Merge Sort
Background knowledge
If you have not read up on how the bubble sort and insertion sort work, and understand their time efficiencies, read those sections first. An appreciation of this will help you understand the purpose behind this approach. Merge sort is a ‘divide and conquer‘ algorithm.
How it works
As you now know, the time efficiency of the bubble sort and insertion sort are both O(n2) – meaning that as the data sets get bigger, the time taken to process the data increases, but by a power of 2.
Merge sort addresses this by breaking the data down from one big list into many small lists, and then recombines them. Although there is more work involved – you have to rebuild all of the lists into one data set – this is more than offset by the saving in time gained by no longer having to sort one large data set.
This image shows how an unsorted list of seven items (pink), is repeatedly split into smaller lists, until there are seven lists of one item each. Note – at this stage, nothing has changed in the ordering of the items.
A merge sort is a recursive algorithm, so although the steps above that take the original list and keep splitting it until there is only one value in each list looks redundant, it is actually important and central to the way in which this algorithm works.
Once the lists can be separated no further, they are recombined, building ever longer lists. It is at this stage that the data is sorted – it is far easier computationally to combine items into a new list in order than it is to rearrange them in situ. In the example above, you can see that after one recombination, there are four lists, three of which contain two values, which are now in order. The process repeats until there is only one list, which will now be in order.
Pseudocode
Wikipedia lists several algorithms for merge sorts. You are not expected at this level to be able to trace it, or write it.
Advantages
More efficient than insertion sort and bubble sort. The order of growth for the merge sort is O(n log n).
Disadvantages
More complex to code, and due to being recursive, more difficult to dry run.