Understanding Merge Sort Algorithm (with Examples in Java)

Merge Sort is one of the most popular sorting algorithms. Many programming languages use either purely Merge Sort or a hybrid algorithm involving Merge Sort for sorting. It is based on the Divide-and-Conquer approach, in which a problem is divided into smaller subproblems and solved individually, then the solutions to the individual subproblems are combined to get the final solution. In Merge Sort, the provided list is recursively divided into two halves, and each half is sorted. Each sorted half is then combined to give a sorted list.

Working of Merge Sort

Suppose we want to sort an array arr. Using the Divide-and-Conquer approach and solving recursively:

Divide

In the divide step, we will recursively divide into halves until it can no longer be divided; until there is only one element in a subarray. Let us call the 0th index of the array start and the last index end. So our array can be represented as arr[start..end]. Suppose the midpoint of the array is mid, then we can divide the array into two halves, arr[start..mid, mid+1..end].

Conquer

Once the array has been divided until we have two subarrays with only one element in each, each subarray is considered to be sorted. We can now merge two subarrays in sorted order. This process continues until all subarrays have been merged.

Let's say we want to sort this array in ascending order.

This is an illustration of the process we would go through if we used Merge Sort.

Implementation of Merge Sort

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void merge (int arr[], int start, int mid, int end){
        // create backups of the two subarrays
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        // copy values into left array
        for(int i = 0; i < left.length; i++){
            left[i] = arr[i+start];
        }

        // copy values into right array
        for(int i = 0; i < right.length; i++){
            right[i] = arr[i+mid+1];
        }

        // maintain pointers to track the current index of the
        // left and right subarrays, and the main array
        int j = start, lIndex = 0, rIndex = 0;

        // set the values from start to end in sorted order, as long
        // as there are still elements in both the left and right subarrays
        while(lIndex < left.length && rIndex < right.length){
            if(left[lIndex] <= right[rIndex]){
                arr[j] = left[lIndex];
                lIndex++;
            }else {
                arr[j] = right[rIndex];
                rIndex++;
            }

            j++;
        }

        // add leftover values from left subarray if any
        while (lIndex < left.length) {
            arr[j] = left[lIndex];
            lIndex++;
            j++;
        }

        // add leftover values from right subarray if any
        while (rIndex < right.length) {
            arr[j] = right[rIndex];
            rIndex++;
            j++;
        }
    }

    static void mergeSort(int arr[], int start, int end){
        // base condition; will execute only if start is less than end,
        // i.e. there's more than element in the array/subarray
        if(start < end){
            // find the midpoint of the array
            int mid = (start + end) / 2;

            // divide further since we have not reached the base case
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);

            // merge the two sorted sections
            merge(arr, start, mid, end);
        }
    }
}

Let's look at the code above.

The mergeSort Method

In the mergeSort method, we find the midpoint of the array, and recursively call mergeSort to sort the left and right subarrays. The code in mergeSort will run until the base condition is met, that is until the subarray contains only one element.

The merge Method

This is the most important part of the merge sort algorithm. In addition to the main array, it takes input indicating the positions of the two sorted subarrays. By knowing start, mid and end, we can represent the left subarray as arr[start..mid] and the right as arr[mid+1..end].
In the merge method, we try to set the values in the main array in sorted order by combining the values from the two subarrays. We start by creating copies of the left and right subarrays. We then create pointers to track the current index of the left and right subarrays, as well as the main array, and loop through the array to set the values from start to end by adding values from the left and right subarrays in sorted order. For instance, the process to merge these two sorted arrays would look like this:

Running the code above will print the following output to the console:

Unsorted array: [8, 2, 6, 4, 9, 1]
Sorted array: [1, 2, 4, 6, 8, 9]

Complexity of Merge Sort

Time Complexity (O(n log n)):

Merge Sort has a time complexity of O(n log n) in all cases, because it always follows the same divide-and-conquer approach whether the array is already sorted or not.

Space Complexity (O(n)):

Merge Sort requires additional memory for temporary arrays used during the merge operation.