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