Merge Sort/Pseudocode

Merge Sort Algorithm Notes

Merge sort algorithm immediately raises the question of GENERICS... To keep it simple, start with sorting integer or string data.

Split the merge sort operation into two functions:

• the main merge sort function
• merge two arrays into a destination array of correct size

Merge Sort Algorithm Pseudocode

Merge two arrays function

The key to writing the mergeTwoArrays() function is to explicitly declare, up front, that the source and destination arrays are correctly sized.

function mergeTwoArrays (array[] s1, array[] s2, array[] dest) {
    n_iterations = length of dest
    for k = 0 to k = n_iterations - 1 {
        if s1[0] < s2[0] {
            front = s1.pop_front()
        } else {
            front = s2.pop_front()
        }
        dest[k] = front    
    }
    return
}

This can be slightly modified so that we do not do a pop operation, but rather keep track of two indices in s1 and s2:

function mergeTwoArrays (arr[] s1, arry[] s2, arr[] dest) {
    n_iterations = length of dest
    i = j = 0
    for k = 0 to k = n_iterations - 1 {
        if s1[i] < s2[j] {
            front = s1[i]
            i += 1
        } else {
            front = s2[j]
            j += 1
        }
        dest[k] = front
    }
    return
}

Merge sort function

Recursive Merge Sort:

Recursive merge sort starts with an input array. It splits the array in half. It recursively calls merge sort on the left and right halves. It then merges the left and right halves into a final result array and returns it.

The base case of this recursive array is if the length of the array to sort is 1 or 0, in which case no recursive call to sort or merge the array halves is needed.

Successively splitting the array to sort into left and right halves; calling merge sort function on each half, merging the sorted halves. To split in half, take the length (number of elements), divide by two, and round up (or down) to nearest integer. This is the midpoint index, but for a 1-based index, since length is 1-based. Subtract 1 to get the midpoint index in a 0-based index schema.

The recursive base case is the length is 1 or 0.