Skip to 0 minutes and 3 secondsNow, 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 secondsAs 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 secondsThe 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 secondsNow, 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 secondsOnce the final merge is complete, the balls end up in a sorted order.

Skip to 3 minutes and 5 secondsSo 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.

10 balls on a shelf, split into 10 sections by dashed purple lines. The balls are, in order, a bowling ball, a pool ball, a cricket ball, a ping pong ball, a baseball, a golf ball, a basketball, a netball, a tennis ball, and a football (soccer ball).

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.

We’ll start with a shuffled set of balls.

10 balls on a shelf. The balls are, in order, a bowling ball, a pool ball, a cricket ball, a ping pong ball, a baseball, a golf ball, a basketball, a netball, a tennis ball, and a football (soccer ball)

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

The same 10 balls on the shelf in the same order as above, but split into two groups of five by a dashed purple line in-between the baseball and the golf ball. The balls are now all contained within a pair of green square brackets. There is an empty shelf below.

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.

The same 10 balls on the shelf. The five balls on the left (bowling ball to baseball) are now contained within a pair of green square brackets. A purple dashed line splits this group of five into a group of two (bowling ball and pool ball) and a group of three (cricket ball, ping pong ball, baseball. There is an empty shelf below.

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.

The same 10 balls on the shelf. A pair of green brackets surround the first two balls (a bowling ball and a pool ball), and there is a dahed purple line separating them. There is an empty shelf below.

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

The top shelf now contains an empty pair of green brackets, followed by a set of three balls (cricket ball, ping-pong ball, baseball) and a set of five balls (golf ball, basketball, netball, tennis ball, soccer ball). The bowling ball and pool ball sit separately on the lower shelf, with a purple arrow pointing at each of them.

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

The balls are all back on the top shelf. The pool ball is now first, followed by the bowling ball. The next three balls, a cricket ball, a ping-pong ball and a baseball, are surrounded by a pair of green brackets. There is a purple dashed line in-between the cricket ball and the ping-pong ball splitting this group into 1 and 2. After the brackets are the remaining five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. The bottom shelf is empty.

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

10 balls on the top shelf. The pool ball is first, followed by the bowling ball, and a small gap before a cricket ball. The next two balls, a ping-pong ball and a baseball, are surrounded by a pair of green brackets. There is a purple dashed line in-between these two balls. After the brackets are the remaining five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. The bottom shelf is empty.

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

There are 8 balls on the top shelf. The pool ball is first, followed by the bowling ball. There is then some empty space contained within a pair of green brackets. After the brackets are the remaining five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. On the bottom shelf are two groups of balls, the first containing just the cricket ball. The other contains the ping-pong ball and the baseball. A purple arrow points at the first ball in each groupon the bottom shelf: the cricket ball and the ping-pong ball.

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.

10 balls on the top shelf. The pool ball is first, followed by the bowling ball. The next three balls, a ping-pong ball, a cricket ball and a baseball, are surrounded by a pair of green brackets, and are in size order. After the brackets are the remaining five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. The bottom shelf is empty.

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

There are 7 balls on the top shelf. A pair of green brackets contain the left half of the shelf, and contains a ping-pong ball, a pool ball, and a gap.  After the brackets are five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. On the bottom shelf are 3 balls in two groups. The left-hand group consists of just a bowling ball, while the right-hand group consists of a cricket ball and a baseball. A purple arrow points at the first ball in each group on the bottom shelf: the bowling ball and the cricket ball.

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.

All 10 balls are on the top shelf. A pair of green brackets contain the left half of the shelf, and contains a ping-pong ball, a pool ball, a cricket ball, a baseball and a bowling ball, so these are in size order. After the brackets are five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. The bottom shelf is empty.

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

All 10 balls are on the top shelf, and contained within a pair of green brackets. The balls are split into two groups, the left-most contains a ping-pong ball, a pool ball, a cricket ball, a baseball and a bowling ball, so these are in size order. The second group contains five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. The bottom shelf is empty.

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.

All 10 balls are on the top shelf. The balls are split into two groups, the left-most contains a ping-pong ball, a pool ball, a cricket ball, a baseball and a bowling ball. The second group is contained within a pair of green brackets, and contains five balls: a golf ball, a basketball, a netball, a tennis ball and a soccer ball. A purple dashed line between the basketball and the netball splits this set of 5 into a group of 2 and a group of 3. The bottom shelf is empty.

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.

The top shelf is entirely contained within a pair of green brackets. The left-hand side of the shelf contains a ping-pong ball, a golf ball, a pool ball, a tennis ball and a cricket ball so these are in size order. The right-hand side of the top shelf is empty. On the bottom shelf are two groups of balls, one of 2 and one of 3. The left-most group consists of a baseball and a bowling ball. The right-most group contains a netball, soccer ball and a basket ball. Purple arrows point at the first ball in each of these two groups: the baseball and the netball.

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

All 10 balls are on the top shelf, in size order. From left to right they are the ping-pong ball, the golf ball, the pool ball, the tennis ball, the cricket ball, the baseball, the netball, the bowling ball, the soccer ball and the basketball.

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.

Use the comments section to ask any question you might have about this algorithm.

Share this video:

This video is from the free online course:

Programming 102: Think Like a Computer Scientist

Raspberry Pi Foundation