Merge Sort/Pseudocode

Merge Sort Algorithm Notes

Merge sort algorithm will require you to know how to do the following:

• Implement an array/list data structure
• How to implement a generics data structure (but start simple with integers or strings if up to you)
• How to implement comparators for custom objects
• How to pop from a data structure (queue-type data structure)
• How to compute ceiling and floor functions
• How to do recursion (and limits to recursion)

Split the merge sort operation into two functions:

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

Recursive Merge Sort Algorithm Pseudocode

Merge two arrays function using pop

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

We can copy s1 and s2 into queue data structures that have peek/pop functionality:

function mergeTwoArrays (array[] s1, array[] s2, array[] dest):
    n_iterations = length(dest)
    q1 = populate queue from s1
    q2 = populate queue from s2
    for k = 0 to k = n_iterations - 1:
        if q1.peek() < q2.peek():
            front = q1.pop()
        else:
            front = q2.pop()

        dest[k] = front

    return

This can be slightly modified so that we do not make copies, 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

Recursive merge sort function

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 method 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 down to the nearest integer. This gives you the element that starts the second half of the array.

Left half = everything up to but not including the mid index, right half = everything including the mid index through the end of the array

function mergeSort( array[] data ):

    // base case:
    if len(data) < 2:
        return data

    // recursive case:

    mid_index = floor( length(data)/2 )

    left_half = data[:mid_index]
    right_half = data[mid_index:]

    left_half = mergeSort(left_half)
    right_half = mergeSort(right_half)

    merge(left_half, right_half, data)

    return data
}

Nonrecursive (Bottom-Up) Merge Sort Algorithm Pseudocode

The bottom-up non-recursive strategy is to merge every successive pair of elements into sorted runs of length two. Then merge these into more sorted runs of length four. Then merge those into sorted runs of length eight, and so on.

Pass i creates all runs of length 2i.

Deploy a second array that stores the merged runs (swap input/output arrays at every iteration).

function merge_sort(S) {
    src = S
    dest = (empty array, size of S)
    for k in log2(length S) {
        we have runs of length i = 2^k
        we are iterating over pairs of runs of length i = 2^k to sort them
        this iteration assembles runs of length 2*i = 2^{k+1}
        for j in range 0 to n, taking strides of size 2*i {
            merge(src, dest, j, i)  // j = where to start, i = stride size, this merges these two halves
        }
    }
}