Java Sorting Algorithms: Merge Sort

Today we are going to analyze one of the most used sorting algorithms: the Merge Sort. It is part of the Divide and Conquer family, just like the  Quick Sort. Merge Sort offers a better performance despite of the Quick Sort since its complexity remains O(n log n) keeping performances. It is also called "algorithm by fusion"

The main defect of the Merge Sort is that it needs auxiliary data structures in order to execute its tasks. We can say that it is a stable and adaptive algorithm, but it is not in-place.

How does it work?

Let's start looking at an image that explains very well how the algorithm works.

If someone has already had to deal with large collections of data to order, the way of working of the algorithm may be already known. The basic idea is the one of dividing the array into small groups and sort them. Once the sorting operation of every subset is completed the minimum element among the elements is taken and it is put into the final array. The process is repeated until every subset contains at least one element.

The foundamental problem is the fusion process.

Fusion algorithm

• The left half of the array is copied on an auxiliary array;
• The minimum element between the auxiliary array and the right half of the array is chosen and the value is copied on the final array;
• The process ends when every element of the auxiliary array has been copied;

Implementation

public class MergeSort 
{ 
    // Merge the two half of arr[]. 
    // The first subset of the array is arr[l..m] 
    // The second subset of the array is arr[m+1..r] 
    public static void merge(int arr[], int l, int m, int r) { 
        // Find the size of the two subarrays to merge
        int n1 = m - l + 1; 
        int n2 = r - m; 

        /* Create auxiliary arrays */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 

        /*Copy data to auxiliary arrays*/
        for (int index=0; index<n1; ++index) 
            L[index] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 

        /* Merge the auxiliary arrays */

        // Starting indexes of the two arrays
        int index = 0, j = 0; 

        // Starting index of the final array
        int k = l; 
        while (index < n1 && j < n2){ 
            if (L[index] <= R[j]) { 
                arr[k] = L[index]; 
                index++; 
            } else{ 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        /* Copy the remaining elements of L[] if any */
        while (i < n1) { 
            arr[k] = L; 
            index++; 
            k++; 
        } 

        /* Copy the remaining elements of R[] if any */
        while (j < n2) { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 

    // Main function that sorts arr[l..r] using 
    // merge() 
    public static void sort(int arr[], int l, int r) { 
        if (l < r) { 
            // Find the middle point
            int m = (l+r)/2; 

            // Sort the first and the second half
            sort(arr, l, m); 
            sort(arr , m+1, r); 

            // Merge the two halves
            merge(arr, l, m, r); 
        } 
    } 

    public static void main(String args[]) { 
        int arr[] = {12, 11, 13, 5, 6, 7}; 

        System.out.println("Unsorted array"); 
        System.out.println(Arrays.toString(arr));

        MergeSort.sort(arr, 0, arr.length-1); 

        System.out.println("Sorted array"); 
        System.out.println(Arrays.toString(arr));
    } 
}