## Want to keep learning?

This content is taken from the Raspberry Pi Foundation & National Centre for Computing Education's online course, Programming 102: Think Like a Computer Scientist. Join the course to learn more.
3.8

## Raspberry Pi Foundation

Skip to 0 minutes and 3 seconds Now, let’s look at another sorting algorithm that is a bit more efficient than the 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 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 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. The unsorted list is first split into two. The algorithm then attempts to merge these two lists.

Skip to 0 minutes and 50 seconds As the first list is unsorted, the algorithm proceeds to apply the Merge Sort 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 two lists are now sorted, because they only have one element in them each. 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 second 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.

Skip to 1 minute and 43 seconds The algorithm returns to the merge code 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.

Skip to 2 minutes and 22 seconds Now, the program 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. As in all the other steps, it emerges the two lists. It removes both sorted list from the original list and begins merging the smallest item from each, one at a time.

Skip to 2 minutes and 56 seconds Once the final merge is complete, the balls end up in a sorted order.

Skip to 3 minutes and 5 seconds So that is the merge sort. In the next step, we’ll have a look at how to implement this in Python. But before you do that, it might be worth having a look back over the entire video and seeing how many steps it took to sort the balls– and compare this with the ball sort we looked at previously. Show your answers in the Comments section below.

# An introduction to merge sorts

Now let’s look at another sorting algorithm, one that is 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 seperated out in 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 a efficient and neat sort which we’ll look at in more detail now.

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

As the first list is unsorted the algorthm 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 a 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. As in all the other steps, 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 a sorted order.

So, that was the merge sort, a recursive algortihm that divides the list up into its smallest parts before gradually re-combining them in ordered sets. In the next step you will explore how to implement this algorithm using python.