Merge Sort in Java

Till now we have discussed sorting algorithm which are though easy to code but are not really efficient when it comes to sorting a large set of objects e.g millions or billions of number. So we need some other algorithms we can be efficient in this case.

Till now the average time complexity of each sorting is O(n*n). Merge Sort has a complexity of O(nlog(n)) for average/worst case as well.

Merge Sort is based on divide and conquer algorithm. It divides the set in equal halves and sort each halves individually and then finally merge both the halves.

The algorithm can be summarized as below

MergeSort(arr[], left,  right)
If right > left
     1. Find the middle point to divide the array into two halves:  
             middle mid = (left+right)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, left, mid)
     3. Call mergeSort for second half:
             Call mergeSort(arr, mid+1, right)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, left, mid, right)

where merge() method is the key which merges the two equal halves assuming both are sorted.

Lets look at the below GIF for a better pictorial representation of Merge Sort



So lets get hands on with Merge Sort by writing a Java Program as below.

import java.util.Arrays;



class MergeSort

{

    void merge(int arr[], int left, int mid, int right)

    {

        int n1 = mid - left + 1;

        int n2 = right - mid;



        int L[] = new int [n1];

        int R[] = new int [n2];



        for (int i=0; i<n1; ++i)

            L[i] = arr[left + i];

        for (int j=0; j<n2; ++j)

            R[j] = arr[mid + 1+ j];



        int i = 0, j = 0;

        int k = left;

        while (i < n1 && j < n2)

        {

            if (L[i] <= R[j])

            {

                arr[k] = L[i];

                i++;

            }

            else

            {

                arr[k] = R[j];

                j++;

            }

            k++;

        }

        while (i < n1)

        {

            arr[k] = L[i];

            i++;

            k++;

        }

        while (j < n2)

        {

            arr[k] = R[j];

            j++;

            k++;

        }

    }



    void mergeSort(int arr[], int l, int r)

    {

        if (l < r)

        {

            int m = (l+r)/2;

            mergeSort(arr, l, m);

            mergeSort(arr , m+1, r);

            merge(arr, l, m, r);

        }

    }

 

    public static void main(String args[])

    {

        int arr[] = {12, 11, 13, 5, 6, 7};

        MergeSort ms = new MergeSort();



        System.out.println("Array before sort " + Arrays.toString(arr));

        ms.mergeSort(arr, 0, arr.length-1);

        System.out.println("Array before sort " + Arrays.toString(arr));

    }

}
//output
//Array before sort [12, 11, 13, 5, 6, 7]
//Array before sort [5, 6, 7, 11, 12, 13]

Analysis of Merge Sort

• Time Complexity: O(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.
• Auxiliary Space: O(n)
• Algorithmic Paradigm: Divide and Conquer
• Sorting In Place: No in a typical implementation
• Stable: Yes

Hope you like it. Stay tune for more interesting sorting algorithms.

Happy Learning !!!

SHARE

Onlinecodegeek