Merge Sort

Overview

Merge Sort is a divide and conquer algorithm. First we divide the array into two parts (left and right) using the middle index of the array to be sorted. Then we sort each part separately and finally combine the parts together in order. Merge sort uses more space compared to Quick Sort as we need to divide the array and store them in separate variables, although there are some implementations of merge sort that use constant space

---

Pseudo Code

• Find middle index of the array (length of array / 2)
• Create two arrays left (0 to middle index) and right (middle index to last index)
• Sort each part individually
  • Note: An array is sorted if there is only one element in the array so we can use this as the base condition for recursion
• Merge two sorted parts together

---

Visualization

The following image from wikipedia will help us visualize the pseudo code

As we can see in the image above first we keep dividing the array into two halves (left and right) till there is only one element in each individual array. At this point we know that all the individual arrays are sorted as there is only one element in each of them. Next we merge the arrays in order till we get the final sorted array.

---

Implementation

public class MergeSortBlog {

    public static void main(String[] args) {
        int[] sampleArray = { 423, 99, 1, 5, 2, 7, 8, 9, 11, 3, 5 };

        mergeSort(sampleArray);
        System.out.println(Arrays.toString(sampleArray));
    }

    //Merge Sort algorithm - recursive
    private static void mergeSort(int[] array) {
        //base condition for recursion
        //array is sorted if there is one or less elements in the array
        if (array.length <= 1)
            return;

        //find middle index of the array
        var middle = array.length / 2;

        //divide arrays into two parts
        int[] left = new int[middle];
        int[] right = new int[array.length - middle];

        for (int i = 0; i < left.length; i++)
            left[i] = array[i];

        for (int i = 0; i < right.length; i++)
            right[i] = array[middle + i];

        //sort left and right part
        mergeSort(left);
        mergeSort(right);

        //merge the array
        mergeArrays(array, left, right);
    }
   
    //Merge the left and right array
    private static void mergeArrays(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j])
                array[k++] = left[i++];
            else
                array[k++] = right[j++];
        }

        while (i < left.length)
            array[k++] = left[i++];

        while (j < right.length)
            array[k++] = right[j++];
    }
}

---

Runtime Complexity

• Time Complexity: O(n log n)
  • Dividing O(log n) – we are halving the array on each recursion
  • Merging O(n)
  • therefore the total complexity is O(n log n)
• Space complexity: O(n) – we need extra space to store the two parts