Divide and Conquer: MergeSort

Alright, now we see some good use of recursion. We know that if we can cut the problem size into half (as in binary search), we can solve the problem quicker. Can we employ this for sorting an array? Well, yes! Let's look into MergeSort. Again the concept is simple- instead of sorting the entire array in one go, we divide the array into two and sort the two smaller arrays instead. Ok, but how do we sort the two arrays?

This is where recursion comes to rescue. We continue to divide the array into ever smaller size until we are left with just one element which is already sorted. Huh, sounds bit hoaky. We need a single sorted array at the end, not n individual elements scattered around. How do we combine these smaller arrays to get the final sorted array?

This is where the merge part comes in. If we have two arrays that are sorted, we can merge these arrays by one pair of elements at a time. For example, if we have two rows of players already ordered by increasing height, we will compare the first player of first row with first player of second row and let in the player who is shorter. The taller of the two waits for the next comparison. We continue to do so until no player is left in any row. Pretty neat, huh!

Pseudocode

function merge(array1, array2)
    m = LENGTH(array1)
    n = LENGTH(array2)
    s = new Array[]
    i = j = k = 0
    while (i < m && j < n)
        if (array1[i] < array2[j])      // compare element-wise and merge
            s[k] = array1[i]
            i = i + 1
        else
            s[k] = array2[j]
            j = j + 1
        k = k + 1
    while (i < m)                       // tack on remaining elements if any
        s[k] = array1[i]
        i = i + 1
        k = k + 1
    while (j < n)                       // tack on remaining elements if any
        s[k] = array2[j]
        j = j + 1
        k = k + 1
    return s

function mergeSort(array)
    n = LENGTH(array)
    if n == 1
        return array
    m = floor((n + 1) / 2)
    L = array[1 : m-1]
    R = array[m : n]
    return merge(mergeSort(L), mergeSort(R))

JavaScript Implementation

//merges two sorted arrays to produce a third sorted array
function merge(array1, array2) {
    var m = array1.length;
    var n = array2.length;
    var s = [];
    var i = j = k = 0;
    while (i < m && j < n)
    {
        if (array1[i] < array2[j])      // compare element-wise and merge
        {
            s[k] = array1[i];
            i += 1;
        }
        else
        {
            s[k] = array2[j];
            j += 1;
        }
        k += 1;
    }
    while (i < m)                       // tack on remaining elements if any
    {
        s[k] = array1[i];
        i += 1;
        k += 1;
    }
    while (j < n)                       // tack on remaining elements if any
    {
        s[k] = array2[j];
        j += 1;
        k += 1;
    }
    return s;

}

//recursively do merge sort
function mergeSort(array) {
    var n = array.length;
    if (n == 1)
        return array;
    var m = Math.floor((n + 1) / 2);
    var L = array.slice(0, m);
    var R = array.slice(m);
    return merge(mergeSort(L), mergeSort(R));
}

Let's test it

a = [5, 4, 10, 9, 8, 1, 2];
console.log(mergeSort(a));

[
  1, 2,  4, 5,
  8, 9, 10
]