An introduction to merge sorts

What is the merge sort algorithm?

The merge sort algorithm uses what’s called a divide and conquer strategy, over the course of the sort the list is separated out into single element lists. Each of these lists is therefore ordered.

They are then repeatedly merged together with their neighbours in order until they join together again as one sorted list.

The merge sort uses a programming technique called recursion, which is where a function calls itself. This nesting of function calls produces an efficient and neat sort which we’ll look at in more detail now.

We’ll start with a shuffled set of balls.

The unsorted list is first split into 2. The algorithm then attempts to merge these two lists.

As the first list is unsorted the algorithm proceeds to apply the mergesort algorithm again by first splitting it and then merging these two new lists.

Once again the first list is unsorted and needs to be split and merged. These 2 lists are now sorted because they have only 1 element.

They can now be removed from the original list, compared, and returned in order.

The program returns to the merge function above and focuses on the 2nd list, this is unsorted and so split and merged.

The Cricket ball is already in a sorted list but the Table Tennis ball and baseball need to be split and merged.

The two ordered sets are removed, compared, and returned in order.

The algorithm returns to the merge call above and can now proceed as it has two sorted lists. The two sets are again removed from the original list, and the first item in each is compared and inserted back into the list.

This comparison is repeated until all the items are replaced in sorted order.

The merge call above now has 2 sorted lists and can merge them. Once again they are removed and the smallest of each set is repeatedly compared until the balls are back in the original list, in order.

Now the algorithm returns to the top-level merge where it has 1 sorted set of balls and 1 unsorted.

It continues with the second, currently unsorted list in the same manner as the first list, splitting and merging until it produces a sorted list.

Now with 2 sorted lists, the algorithm can complete its final merge. It merges the two lists. It removes both sorted lists from the original list and begins merging the smallest item from each list 1 at a time.

Once the final merge is complete the balls end up in sorted order.

So, that was the merge sort, a recursive algorithm that divides the list up into its smallest parts before gradually re-combining them in ordered sets.