Skip main navigation

An introduction to merge sorts

This video and article offers an animated example of a merge sort, narrated by James Robinson. Let's explore.

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.

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 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 algorithm 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 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. 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 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 algorithm that divides the list up into its smallest parts before gradually re-combining them in ordered sets.

This article is from the free online

Programming 102: Think Like a Computer Scientist

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education