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

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 of 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
}

Merge sort function - recursive

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
}

other approaches:

• you can also have a public method that takes an array, and a private method that copies the array into some other data structure (for example, a queue or a stack) to make it easier to pop elements/etc
• you can either make left and right halves a copy,
• or you can... make your algorithm do an in-place shuffle that would get more complicated