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

NOTE: this will require you to be able to do rounding (math.ceil, math.floor).

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