Programming 12: Merge Sort Algorithm

2n) 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).]]>