Merge Sort

Test yourself on Merge Sort with exam style questions, marked instantly.

Flashcards that come back just before you would forget them.

A revision plan that remembers what you know and shows what to do next.

See which topics you have nailed and which need another look.

Quiz yourself on Merge SortGet your flashcardsBuild my revision planTrack my progress

Split It, Sort It, Join It

Merge sort is like sorting a huge pile of exam papers with friends. You split the pile in half, then split again, until everyone holds a single paper (one paper is already sorted). Then you pair up and merge the small sorted piles into bigger sorted piles, until one sorted pile is left.

Three worked examples that sort the list 5, 3, 8, 1, 4. Bubble sort rows: after pass 1 the list is 3 5 1 4 8, after pass 2 it is 3 1 4 5 8, and after pass 3 it is 1 3 4 5 8. Merge sort divides the list into 5 3 and 8 1 4, then into 5, 3, 8 and 1 4, then into single items. It then merges 5 and 3 into 3 5, merges 1 and 4 into 1 4, merges 8 with 1 4 into 1 4 8, and merges 3 5 with 1 4 8 into 1 3 4 5 8. Insertion sort inserts 3, 8, 1 and 4 in turn, so the sorted part on the left grows until the list is 1 3 4 5 8. Sorted items are green and bold.

Bubble sort compares neighbouring items and swaps them if they are in the wrong order, then repeats the pass. Merge sort divides the list down to single items, then merges the sorted parts back together. Insertion sort inserts each item into the sorted part. On long lists bubble sort and insertion sort make many comparisons, and merge sort makes fewer. Bubble sort and merge sort are named by OCR, AQA and Edexcel. Insertion sort is named by OCR only.

Merge Sort or Bubble Sort?

Feature Merge Sort Bubble Sort
Method Divide the list, then merge sorted lists Compare neighbours and swap
Speed on large lists Much faster Slow
Extra memory Needs extra space for the lists it merges None, it sorts in place
Ease of coding Harder to program Simple

Deep Dive: The Two Stages

  1. Divide: split the list into two halves. Keep splitting each half until every list holds one item. A list of one item is already sorted, so splitting stops.
  2. Merge: combine two sorted lists into one sorted list. Compare the front items of both lists, take the smaller one, and repeat until both lists are empty. Keep merging until one list is left.

Merge sort uses divide and conquer, which means breaking a big problem into smaller ones that are easier to solve.

Deep Dive: Merge Sort Trace

Sort [6, 2, 8, 4]:

Divide:

  • [6, 2, 8, 4] splits into [6, 2] and [8, 4]
  • [6, 2] splits into [6] and [2]. [8, 4] splits into [8] and [4].

Merge:

  • Merge [6] and [2]: compare 6 and 2, take 2, then 6. Result [2, 6].
  • Merge [8] and [4]: compare 8 and 4, take 4, then 8. Result [4, 8].
  • Merge [2, 6] and [4, 8]: compare 2 and 4, take 2. Compare 6 and 4, take 4. Compare 6 and 8, take 6. Only 8 is left, take 8.
  • Result: [2, 4, 6, 8]

Deep Dive: Merging Two Lists

Merge [2, 5] with [1, 4]:

CompareTakeMerged list so far
2 and 11[1]
2 and 42[1, 2]
5 and 44[1, 2, 4]
Only 5 left5[1, 2, 4, 5]

For an 8 item list, the splits give 2 lists of 4, then 4 lists of 2, then 8 lists of 1. That is three divisions.

Memory Trick

Split, split, split, then merge, merge, merge. Divide until every list has one item, then build the sorted list back up.
Merge always takes the smaller front item when sorting into ascending order.

Exam Tips

  • Show both stages: draw the divide steps and then the merge steps.
  • Merge advantage: much faster than bubble sort on large lists.
  • Merge disadvantage: needs extra memory and is harder to program.
  • Common mistake: sorting the halves while splitting. Nothing is sorted until the merge stage.

Make this stick

Signing in gives access to all PrepWise features.

PrepWise is a trading name of A3M Quality Solutions Limited, registered in England and Wales, company number 14959172. Registered office: 202 Stroud Road, Gloucester, GL1 5LA. ICO registration ZC267069.