The Merge Sort Algorithm

Merge Sort: Basic Idea

The idea of this sorting algorithm is simplicity itself: Split the original sequence into two "equal" parts, sort each part, and then "merge" the two sorted parts back together. Of course each of the subsequences may have to have the same thing done, giving rise to a recursive algorithm.

Merge Sort: Name, Input and Output

Name: SortByMerge

Input:

• A sequence of values, all of a given type, which is called s
• Two positions in the sequence, to determine the range of values within the sequence that will be sorted, which are called firstPosition and lastPosition, and which satisfy firstPosition <= lastPosition

Output:

• The sequence of values s, sorted in ascending order between firstPosition and lastPosition, inclusive

Merge Sort: Pseudocode

Algorithm SortByMerge(s, firstPosition, lastPosition)
=====================================================
if (firstPosition < lastPosition)
    middlePosition = (firstPosition + lastPosition) / 2
    SortByMerge(s, firstPosition, middlePosition)
    SortByMerge(s, middlePosition+1, lastPosition)
    Merge(s, firstPosition, middlePosition, middlePosition+1, lastPosition)

See here for an example (a pdf document).

Pseudocode for Function Merge of Merge Sort

In the following pseudocode, for simplicity, we refer to all the elements of the sequence from firstPosition to middlePosition as "firstPart", and all elements of the sequence from middlePosition+1 to lastPosition as "secondPart".

Algorithm Merge(s, firstPosition, middlePosition, middlePosition+1, lastPosition)
=================================================================================
Declare a temporary sequence to store the elements
while both firstPart and secondPart remain non-empty
    if next element of firstPart < next element of secondPart
        Copy next element of firstPart to temporary sequence
        Increment position pointers in both firstPart and temporary sequence
    if next element of firstPart >= next element of secondPart
        Copy next element of secondPart to temporary sequence
        Increment position pointers in both secondPart and temporary sequence
endwhile
if firstPart non-empty copy remaining elements of firstPart to temporary sequence
if secondPart non-empty copy remaining elements of secondPart to temporary sequence
Copy temporary sequence back to original sequence

Note that this is the first algorithm we have seen which requires an amount of additional storage equal to the amount of storage for all of the original data (in addition to the small amount of additional storage for the usual small number of auxiliary variables for moving data around).

Merge Sort: Performance

We give an informal argument (rather than a formal proof) to try to convince you that the complexity of the Merge Sort is O(n*log n).

First, we note that each time the algorithm is called, two things happen:

• The splitting of the input sequence into two (equal, or nearly equal) parts, which is a O(log n) operation, by the same arguments used in the discussion of binary search
• The merging of those two sorted parts, which involves comparisons on all the elements (a O(n) operation) and copying all the elements (also a O(n) operation), which implies that the merge itself is a O(n) operation

The fact that for each split (of the approximately log n splits) there is a merge (requiring about 2n operations) means that there are approximately 2n*(log n) operations required in all, from which we may reasonably infer that the Merge Sort is O(n*log n).