In this post I will implement well known divide and conquer sorting algorithm – Merge Sort. The idea of the algorithm is as follows:

• recursively divide unsorted list into two sub-lists
• continue until each sub-list contains 1 element
• recursively merge them back in the right order

We can visualize merge sort algorithm by sorting following list [3 5 4 7 2 1]. I’ll use colors to specify current split list and current merge elements.

Split Iteration #1 [3 5 4 7 2 1] → [3 5 4] [7 2 1] [3 5 4] [7 2 1] → [3] [5 4] [7 2 1] [3] [5 4] [7 2 1] → [3] [5 4] [7 2 1]

Merge Iteration #1 [3] [5 4] [7 2 1] → [3] [5 4] [7 2 1]

Split Iteration #2 [3] [5 4] [7 2 1] → [3] [5] [4] [7 2 1]

Merge Interation #2 [3] [5] [4] [7 2 1] → [3] [4 … [3] [5] [4] [7 2 1] → [3] [4 5] [7 2 1]

Merge Iteration #3 [3] [4 5] [7 2 1] → [3 … [3] [4 5] [7 2 1] → [3 4 … [3] [4 5] [7 2 1] → [3 4 5] [7 2 1]

Split Iteration #3 [3 4 5] [7 2 1] → [3 4 5] [7] [2 1] [3 4 5] [7] [2 1] → [3 4 5] [7] [2 1]

Merge Iteration #4 [3 4 5] [7] [2 1] → [3 4 5] [7] [2 1]

Split Iteration #4 [3 4 5] [7] [2 1] → [3 4 5] [7] [2] [1]

Merge Iteration #5 [3 4 5] [7] [2] [1] → [3 4 5] [7] [1 … [3 4 5] [7] [2] [1] → [3 4 5] [7] [1 2]

Merge Iteration #6 [3 4 5] [7] [1 2] → [3 4 5] [1 … [3 4 5] [7] [1 2] → [3 4 5] [1 2 … [3 4 5] [7] [1 2] → [3 4 5] [1 2 7]

Merge Iteration #7 [3 4 5] [1 2 7] → [1 …] [3 4 5] [1 2 7] → [1 2 …] [3 4 5] [1 2 7] → [1 2 3 …] [3 4 5] [1 2 7] → [1 2 3 4 …] [3 4 5] [1 2 7] → [1 2 3 4 5 …] [3 4 5] [1 2 7] → [1 2 3 4 5 7]

Implementation of the merge sort heavily rely on sort and merge functions:

Complexity: O(n·logn).