GCSE · Computer Science · Edexcel · Spec 1CP2

Merge sort

Handed a huge pile of exam scripts to sort? Merge sort’s trick sounds like cheating: break the pile into bits so small they’re already sorted, then rebuild it carefully.

Watch it run

Seven numbers come apart, then come back in order

A merge sort of 43, 21, 14, 50, 64, 3, 19. The method is on the left. Underneath, the list builds up stage by stage.

Before you press Next: do you think the list gets any more sorted while it’s being split?

 1  split each list in the middle
 2  odd length? first list gets middle
 3  repeat until every item is alone
 4  merge neighbouring pairs of lists
 5  no partner? copy it down
 6  repeat until one list is left

Variables

lists=1phase=startlongest list=7

Output

start    43 21 14 50 64 3 19

Step 1: Here’s the whole unsorted list. Merge sort begins by splitting it. Keep an eye on the order of the numbers while it does.

1 / 8

Press Next to go one stage at a time, or Play to watch the whole sort run.

Step 1 of 8: Here’s the whole unsorted list. Merge sort begins by splitting it. Keep an eye on the order of the numbers while it does..

Watch out: When a list has an odd number of items, the first list takes the middle item. That’s why 50 goes into the first list at the first split, and why 3 goes with 64 when 64, 3, 19 is split.

Where does the sorting happen?

Be honest: what do you think?

Merge sort has two phases: splitting, then merging. By the end, the list is in order.

Which of these is closest to what you think right now?

The splitting does the sorting. Each split puts the items a bit more in order.The merging does the sorting, but merging just means joining two lists end to end.The merging does the sorting. Each merge compares the front items of two sorted lists and moves the lower one across.

How sure are you?

I'm sureI think soI'm guessing

The splitting does the sorting. Each split puts the items a bit more in order.

This is a common misconception

It’s a really common thought, but look back at the splits: 43, 21, 14, 50 and 64, 3, 19 are in exactly the same jumbled order as before. A split just cuts a list in the middle. Nothing is compared and nothing moves. Splitting only stops when every item is in a list of its own, and a list of one item is already sorted. That’s the whole point of it.

The merging does the sorting, but merging just means joining two lists end to end.

This is a common misconception

You’ve got the right phase but the wrong move. If you joined 21, 43 and 14, 50 end to end you’d get 21, 43, 14, 50, which isn’t in order. A real merge compares the front items of the two lists and moves the lower one into the new list, again and again. Only when one list is empty do you copy the rest of the other list across.

The merging does the sorting. Each merge compares the front items of two sorted lists and moves the lower one across.

This matches the evidence

Exactly right. Splitting breaks the problem down until each piece is so small it’s already solved: one item, already sorted. Merging then builds the answer back up, and every merge produces a longer sorted list from two shorter ones. Breaking a problem into smaller and smaller parts until they’re simple enough to solve directly is called divide and conquer, and merge sort is a divide and conquer algorithm.

Divide and conquer: split until each list holds one item, which is already sorted, then merge pairs of sorted lists until one ordered list is left.

Your turn: one merge

Merge two sorted lists yourself

Merge the sorted lists 4, 6, 7 (list 1) and 2, 5, 9 (list 2) into one sorted list.

Make an empty list for the merged items. The front items are 4 (list 1) and 2 (list 2).
missing step

Which line is step 2?

4 is in list 1, so move 4 first. Merged: 42 is lower than 4, so move 2. Merged: 24 is higher than 2, so move 4. Merged: 4

Spot the mistake

Something goes missing

Sort 35, 12, 48, 7, 26, 51, 9 into ascending order using a merge sort. Show every stage.

A student’s answer — which line goes wrong?

Start: 35 12 48 7 26 51 9
Split 1: [35 12 48 7] [26 51 9]
Split 2: [35 12] [48 7] [26 51] [9]
Split 3: [35] [12] [48] [7] [26] [51] [9]
Merge 1: [12 35] [7 48] [26 51]
Merge 2: [7 12 35 48] [26 51]
Merge 3: [7 12 26 35 48 51]

Merge sort or bubble sort?

Merge sortvsBubble sort

Tap a row to see why it matters.

Focus

Speed on a large data set

Merge sort

Generally much faster

Bubble sort

Generally much slower

The insight

This is merge sort’s big selling point, and its speed advantage shows most on large data sets.

Memory needed

Merge sort

More, because new lists are made each time a list is split or two lists are merged

Bubble sort

Less than merge sort

How hard it is to write

Merge sort

More complex

Bubble sort

Simpler

Speed on a small data set

Merge sort

Can be slower, because the data has to be broken apart first

Bubble sort

Can be faster, because it avoids merge sort’s overhead of breaking the data apart

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Break the list apart until every item stands alone. Then build it back up, in order, one merge at a time.

What you need to know

Merge sort is a sorting algorithm with two phases: splitting, then merging.
Splitting: a list is split in the middle into two lists. This repeats until every item is in a list of its own. If a list has an odd number of items, the first list takes the middle item.
A list of one item is already sorted, so that is where splitting stops.
Merging combines two sorted lists into one longer sorted list. Compare the first items of the two lists and move the lower one into the merged list. When one list is empty, copy the items left in the other list across in order.
In the merging phase, lists are merged one pair at a time, stage by stage, until one ordered list is left. A list with no partner at a stage is copied down to the next stage.
Merge sort is a divide and conquer algorithm: it breaks a problem into smaller and smaller parts until they are simple enough to solve directly.
Compared with bubble sort, merge sort is generally much faster, especially on large data sets. But it is more complex to write and needs more memory, because new lists are made at every split and merge. On small data sets, simpler algorithms such as bubble sort can be faster.

The big picture

Merge sort puts a list in order in two phases. Splitting cuts each list in the middle, with the first list taking the middle item when the length is odd, until every item stands alone. Merging then combines pairs of sorted lists stage by stage: compare the front items, move the lower one, and copy the rest across when one list empties. A list with no partner at a stage is copied down. Merge sort is a divide and conquer algorithm: generally much faster than bubble sort, especially on large data sets, but more complex to write and it needs more memory.

Key points

1Split in the middle until every item stands alone. Odd number of items? The first list gets the middle one.

2Splitting puts nothing in order. All of the sorting happens during merging.

3To merge: compare the two front items, move the lower one, and copy the rest across when one list runs out.

4No partner at a stage? Copy that list down to the next stage.

5Faster than bubble sort on large data sets, but more memory and more complex to write.

.we-_R_18slubsnpfiv5ubrb_ [data-we-step]{display:flex !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-solution]{display:block !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-reveal]{display:none !important}

Worked example

Problem

Use a merge sort to put 9, 4, 7, 1 into ascending order. Show each stage, and the comparisons in the final merge.

⚠ Watch out

Treating a merge as joining two lists end to end. A merge compares the front items of the two lists and moves the lower one, again and again. Only when one list is empty is the rest of the other list copied across.

🧠

Memory hook

Two queues, each lined up shortest to tallest, merge through one door: the shorter of the two front people always goes next, and when one queue runs out, the rest walk through. That’s a merge. Merge sort breaks the crowd into queues of one, then merges them back in pairs.

✓

Check yourself

Without looking back, explain why merge sort bothers to split a list all the way down to single items, even though splitting doesn’t put anything in order.

Flashcards

(14)

What is merge sort?

A sorting algorithm that repeatedly splits data into smaller lists, then merges pairs of lists, putting the items in order as they are merged.

What are the two phases of merge sort?

Splitting, then merging.

How does the splitting phase work?

Each list is split in the middle into two lists, and this repeats until every item is in a list of its own.

A list with an odd number of items is split. Which list gets the middle item?

The first list.

Why does splitting stop when every item is on its own?

A list of one item is already sorted.

What does merging do?

It combines two already sorted lists into one longer sorted list.

During a merge, how do you decide which item moves next?

Compare the first items of the two lists and move the lower one into the merged list.

During a merge, one list becomes empty. What happens next?

Copy each item left in the other list into the merged list, in order.

At a stage of merging, one list has no partner. What happens to it?

It is copied down to the next stage of merging.

When does the merging phase end?

When all the lists have been merged into one ordered list.

What is a divide and conquer algorithm?

One that breaks a problem into smaller and smaller parts until they are simple enough to solve directly.

On a large data set, how does merge sort usually compare with bubble sort for speed?

Merge sort generally performs much faster.

Why does merge sort need more memory than bubble sort?

New lists are made each time a list is split or two lists are merged.

Why can bubble sort be faster than merge sort on a small data set?

Merge sort has the overhead of breaking apart the data before it can sort it.

Tap any card to flip it, or use Study as deck to go through them one at a time. In the full lesson these run as a spaced-repetition deck — you rate each card Hard, Good or Easy and the tricky ones keep coming back until they stick.

Learning with Lightbulb is opening soon

You can use this lesson now. Join the waitlist and we'll let you know when the full Lightbulb experience is ready.

Keep me posted

Seven numbers come apart, then come back in order

Be honest: what do you think?

Merge two sorted lists yourself

Something goes missing

More Edexcel GCSE Computer Science topics