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

Now that we can merge two arrays, let's get to the merge sort method.

We start with a recursive version of merge sort. (Base case, recursive case.)

Each time we split the left and right halves, we call the merge sort function on each half, then merge them together.

How do we split in half? Take the length, divide by two; the length is starting at 1, so we divide it by two to get the midpoint, then subtract 1 to get the midpoint index in a 0-based schema.

Base case: length of the array to sort is 1