When faced with a large task, it can help to break it down into smaller tasks and solve those one at a time; this is the main idea behind divide and conquer algorithms. When sorting a list, these types of algorithms often are very efficient at what they do. A great example of a divide and conquer sorting algorithm is Merge Sort.

Assumptions

What is Merge Sort?

Merge Sort, sometimes spelled mergesort, is a divide and conquer sorting algorithm that works by repeatedly splitting an array in to two halves until each array contains only one element, and then the algorithm "merges" the arrays back together in sorted order. > Most implementations of Merge Sort are stable, however the most common implementations are also not in place. The implementation shown will not be in place.

/* pseudo-code */
int[] arrClone;

function sort(int [] arr) {
    arrClone = arr.copy();
    MergeSort(arr, 0, arr.length - 1);
}

function MergeSort(int[] arr, int low, int high) {
    if(low < high) {
        // Find the midpoint;
        int mid = (low + high) / 2;
        // Sort the left half.
        MergeSort(arr, low, mid);
        // Sort the right half.
        MergeSort(arr, mid + 1, high);
        // Merge the two halves.
        merge(arr, low, mid, high); 
    }
}

function merge(int[] arr, int low, int mid, int high) {
    int i,j,k;
    i = low;
    j = mid + 1;
    // Copy the contents of arr into arrClone.
    for(k = low; k <= high; k++) {
        arrClone[k] = arr[k];
    }
    // Loop through the array.
    for(k = low; k <= high; k++) {
        // 1.
        if ( i > mid ) {
            arr[k] = arrClone[j];
            j++;
        }
     // 2.
        else if ( j > high ) {
            arr[k] = arrClone[i];
            i++;
        }
     // 3.
        else if ( arrClone[i] > arrClone[j] ) {
            arr[k] = arrClone[j];
            j++;
        }
     // 4.
        else {
            arr[k] = arrClone[i];
            i++;
        }
    }
}

Here is a breakdown the logic of merge:

  1. i < mid: if we've crossed from the low over the mid of the two halves, then the right side is all that is left to add elements from.
  2. j > high: This asks if we've crossed over the right half of the array with that pointer, to which only the left side has elements remaining to place.
  3. arrClone[i] > arrClone[j]: if 1 and 2 are false, then we compare the elements in the positions i and j and place the smaller element into the array.
  4. else: This else case is to cover the alternate case of 3; the else statement here compares positions i and j and places the smaller of the two elements. Here, arrClone[i] is placed, where in 3, arrClone[j] is placed.

Merge Sort Analysis

Worst Memory
O(n log n) O(n)

Recalling <a href="https://www.devMaking.com/learn/algorithms/master-theorem/" target="_blank" style="color:inherit;">The Master Theorem</a>:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">T(n) = aT( n/b ) + O(n<sup>d</sup>)</div> <br>

Taking this step by step:

  • The array is split in half: b = 2.
  • The left and right halves are sorted: a = 2.
  • The two halves are merged back together: O(n), d = 1.

Representing this by the master theorem results in T(n) = 2T(n/2) + O(n).

When we plug these numbers into the equation:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">d ? log<sub>b</sub>a is 1 = log<sub>2</sub>2</div> Therefore, we know that the resulting formula is:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">n<sup>d</sup>log<sub>b</sub>n = n<sup>1</sup>log<sub>2</sub>n</div> Which evaluates to a final result of

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">O(n log n)&#8718;</div> <br>

> Merge Sort is an optimal sorting algorithm according to Big-O, however faster algorithms exist due to the hidden coefficients.

Merge Sort Conceptualization

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_MergeSort_01.png" alt="unsorted array" style="max-width:95%;">

</div>

Starting with an array, we split it into two halves.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_MergeSort_02.png" alt="split-once unsorted array" style="max-width:95%;">

</div>

We continue to do this with all the arrays until they are all of length 1.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_MergeSort_03.png" alt="fully-split unsorted array" style=";max-width:95%;">

</div>

From here, we merge all of the single items into lists of two, then those lists into lists of four, until we have a complete sorted array.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_MergeSort_04.png" alt="merged and sorted array" style="max-width:95%;">

</div>

When to use Merge Sort

Merge sort is one of the best to use for general-purpose sorting as it has a worst case complexity of O(n log n). This is nice for large sets of data compared to other sorting algorithms such as selection and insertion sort. > Merge sort is one of the algorithms used in Timsort, which blends together mergesort and insertion sort to achieve better runtimes on average than merge sort.

Further Resources