Programming 12: Merge Sort Algorithm

The merge sort algorithm is one of the fastest algorithms that exists for sorting arrays. Consider the following algorithm and example for sorting the array that contains (3, 4, 1, 5, 2, 7, 6}. Despite its complicated algorithm, merge sort is the fastest algorithm at O(n log2n) compared to selection, insertion and bubble sorts at O(n2).

Step 1. Split each element in the original array into separate arrays of one element.

  • (3, 4, 1, 5, 7, 2, 6) → (3) (4) (1) (5) (7) (2) (6)

Pass 1: (3) (4) (1) (5) (7) (2) (6)

Step 2. Pair off each neighbouring array. If there are odd number of arrays, it pairs with an empty array.

Pass 1:

  • Pair 1:  (3) (4)
  • Pair 2: (1) (5)
  • Pair 3: (7) (2)
  • Pair 4: (6) ( )

Step 3. For each pair, set the “pivots” (as indicated by * asterisk)  to the first elements of the arrays. The elements with pivots are the two numbers that we will compare.

  • Pass 1 – Pair 1: (3*) (4*)

Step 4. Compare the two pivoted numbers. Move the smaller of the two numbers into the the first element of a new array (i.e. merged array, as indicated by array after : colon). For the array from which you moved the number, move the pivot over to the next element if it exists; if no more number exists in this array, copy the rest of the non-empty array to the end of the merged array. (Note: This step looks simple on the first pass when there are only two numbers. On the second and subsequent pass, there will be a move in pivots).

  • Pass 1 – Pair 1: (3*) (4*) : ( ) → ( ) (4*) : (3) → ( ) ( ) : (3, 4)

Step 5. Repeat Steps 3 and 4 for the next pairs within the pass.

  • Pass 1 – Pair 2: (1*) (5*) : ( ) → () (5*) : (1) → ( ) ( ) : (1, 5)
  • Pass 1 – Pair 3: (7*) (2*) : ( ) → (7*) () : (2) → (2, 7)
  • Pass 1 – Pair 4: (6*) ( ) : ( ) → ( ) ( ) : (6)

Step 6. Repeat Step 2 for the next pass until done.

Pass 2: (3, 4) (1, 5) (2, 7) (6)

From Step 2 above …

Pass 2:

  • Pair 1: (3, 4) (1, 5)
  • Pair 2: (2, 7) (6)

From Steps 3 to 5 above …

  • Pass 2 – Pair 1: (3*, 4) (1*, 5) : ( ) → (3*, 4) (5*) : (1) → (4*) (5*) : (1, 3) → ( ) (5*) : (1, 3, 4) → ( ) ( ) : (1, 3, 4, 5)
  • Pass 2 – Pair 2: (2*, 7) (6*) : ( )  → (7*) (6*) : (2) → (7*) ( ) : (2, 6) → ( ) ( ) : (2, 6, 7)

From Step 6 above …

Pass 3: (1, 3, 4, 5) (2, 6, 7)

From Step 2 Above …

Pass 3:

  • Pair 1: (1, 3, 4, 5) (2, 6, 7)

From Steps 3 to 5 Above … 

  • Pass 3 – Pair 1: (1*, 3, 4, 5) (2*, 6, 7) : ( ) → (3*, 4, 5) (2*, 6, 7) : (1) → (3*, 4, 5) (6*, 7) : (1, 2) → (4*, 5) (6*, 7) : (1, 2, 3) → (5*) (6*, 7) : (1, 2, 3, 4) → ( ) (6*, 7) : (1, 2, 3, 4, 5) → ( ) ( ) : (1, 2, 3, 4, 5, 6, 7)

Done! The resulting sorted array is (1, 2, 3, 4, 5, 6, 7).

Note: Despite having 7 numbers, the merge sort only has 3 passes (compared to the other at O(n2) sorts that would have 6 passes for the same example).