Merge Sort in Java

by

Merge Sort in Java. Merge sort is a popular sorting algorithm known for its efficiency and reliability. Merge sort follows the divide and conquer approach, breaking down the sorting task into smaller sub-problems until the base case is reached, and merging the sorted solutions to form the final sorted array. In this article we will write code for merge sort in java.

Overview of Merge Sort Algorithm

Merge Sort operates by recursively dividing the input array into two halves until each subarray contains only one element. then it merges those sorted subarrays to produce a fully sorted array. The key steps of merge sort include-

  • Divide- Split the unsorted array into half.
  • Conquer- Recursively apply merge sort to each sub-array until they are reduced to a single element.
  • Combine- Merge this sorted sub-array to produce the final sorted array.

Merge Sort Program in Java

public class MergeSort {
    // function to merge sub array
   public static void merge(int array[], int left, int middle, int right)
    {
        int i, j, k;
        int n1 = middle - left + 1;
        int n2 = right - middle;
        // creating temporary arrays
        int[] leftArray = new int[n1]  ;
        int rightArray[] = new int[n2];
        // copy data to temporary array left array and right array
        for (i = 0; i < n1; i++)
        {
            leftArray[i] = array[left + i];
        }
        for (j = 0; j < n2; j++)
        {
            rightArray[j] = array[middle + 1 + j];
        }
        // merge the temporarry array back into array
        i = 0;
        j = 0;
        k = left;
        while (i < n1 && j < n2)
        {
            if (leftArray[i] <= rightArray[j])
            {
                array[k] = leftArray[i];
                i++;
            }
            else
            {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        // copy the remaining elements of left array if there are any
        while (i < n1)
        {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        // copying the remaining element of rigth array if there are any.
        while (j < n2)
        {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
    // Recursive function to perfrom merge sort on array
    public static void mergeSort(int array[], int left, int right)
    {
        if (left < right)
        {
            int middle = left + (right - left) / 2;
            // Recursively sort the first and second half
            mergeSort(array, left, middle);
            mergeSort(array, middle + 1, right);
            // merge the sorted half
            merge(array, left, middle, right);
        }
    }

    public static void main(String[] args) {

        int array[] = {2, 5, 8, 9, 23, 25, 56, 78, 876};
        int arraysize = array.length;
        System.out.println("Given array");
        for (int i = 0; i < arraysize; i++)
        {
            System.out.print(array[i]+" ");
        }
        mergeSort(array, 0, arraysize - 1);
        System.out.println("\nArray after sorting ");
        for (int i = 0; i < arraysize; i++)
        {
            System.out.print(array[i]+" ");
        }
    }
}

Output

Merge Sort Program in Java

In the above C program

  • The merge function combines two sorted sub-arrays into a single sorted array.
  • The mergeSort function recursively divides the array into two halves and calls the merge function two to merge the sorted halves.
  • The main function initializes an array, calls mergeSort to sort the array, and prints the sorted array.

Merge Sort Time Complexity

Merge Sort’s time complexity is consistently effective and is expressed as O(n logn), Where n is the number of elements in the array to be sorted. The complexity of merge sort makes merge sort a reliable choice for sorting large data sets, As it maintains a relatively consistent performance regardless of input size.

Happy Coding & Learning

See Also

Leave a Comment