3.10.mp4Now I’d like to show you another sorting algorithm that is also a little bit more efficient than bubble sort.
The merge sort algorithm uses what’s called a divide-and-conquer strategy. Over the course of the sort, the list is separated out in single element lists. Each of these lists is 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. Let’s look at this in more detail.
The merge sort algorithm involves two things:
Splitting lists into two halves
Merging two sorted lists into one sorted list
To start with, the unsorted list is split, again, and again into smaller and smaller lists. Like in the example below.
[4,7,3,1,9,3,1]
/ \
[4,7,3][1,9,3,1]
/ \ / \
[4][7,3][1,9][3,1]
/ / \ / \ / \
[4][7][3][1][9][3][1]
When there is only one item in each list, the algorithm begins merging them back together, making sure the remerged lists are sorted. Next, I will walk you through a worked example to help illustrate this.
I will start with a shuffled set of balls.
The unsorted list is first split into two. Each of these lists is passed into another merge sort algorithm. This is the recursion I spoke about earlier. At first, I will just follow the left sublist’s journey.
The merge sort algorithm again splits the list and then passes each half into its own copy of the merge sort algorithm.
Once again, the list is split and another merge sort algorithm is called, but these two lists are sorted, because they have only one element.
They can now be merged. To show you how this works, I will move them onto the shelf below. The two balls are compared and then returned to the shelf in the correct order. This version of the merge sort algorithm has done its job and the list is passed back to the previous merge sort (the one that called this version).
The program returns to the merge function above and focuses on the second list. This is unsorted and so is 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 a sorted order.
The merge call above now has two 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 one sorted set of balls and one 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 two sorted lists the algorithm can complete its final merge. It removes both sorted lists from the original list and begins merging the smallest item from each list one at a time.
Once the final merge is complete the balls end up in a sorted order.
So, that was the merge sort, a recursive algorithm that divides the list up into its smallest parts before gradually recombining them in ordered sets. In the next step, you will explore how to implement this algorithm using Python.