Merge sort: divide and conquer
Split a list of eight numbers in half again and again until every part holds one number, then merge the parts back, always taking the smaller front number. Count the comparisons and compare them with bubble sort and insertion sort on jumbled, sorted and reversed lists.
Core concept
Merge sort divides the list into halves until each part has one number, then merges sorted parts by always taking the smaller front number; its comparisons grow like n log n, far slower than the n² of bubble sort
Topic: Algorithms
Merge sort uses an idea called divide and conquer: a big problem is split into small problems that are easy to solve, and their answers are put together. A list of one number is already sorted, so merge sort keeps splitting the list in half until every part has just one number. Then it merges the parts back in pairs. To merge two sorted parts, it looks only at the front number of each and takes the smaller one, again and again, until both parts are used up. Because every merge only walks along the parts once, and the list can be halved only a few times (8 halves to 4, 2 and 1 in three splits), merge sort makes about n × log₂ n comparisons. Bubble sort and insertion sort can need n × (n − 1) ÷ 2, which grows much faster as the list gets longer.
What you will learn
- Explain how merge sort splits a list down to single numbers.
- Merge two sorted lists by taking the smaller front number each time.
- Compare the comparisons of merge sort, bubble sort and insertion sort on the same list.
- Explain why merge sort is faster on long lists.
Before you start
- Know bubble sort or insertion sort, and what a comparison is.
Materials
- Eight numbered cards, to split and merge by hand
Equipment
- None
Procedure
- Run merge sort on the jumbled list and count its comparisons.
- Run bubble sort on the same list and compare.
- Sort the reversed list both ways.
- Answer the practice challenges.