Sorting algorithms: bubble, insertion, merge and quick sort
Sorting puts data in order so it can be searched and displayed efficiently. You need to trace each standard algorithm by hand and compare how their running times grow as the data gets larger.
Part 1 of 3: Learn it
In short
- Bubble and insertion sort are simple but O(n²) in the worst case.
- Merge sort splits the list in halves and merges sorted halves: O(n log n) every time.
- Quick sort partitions around a pivot: O(n log n) on average, O(n²) at worst.
Where this is in your specification
Spec points: AQA 7517 4.3.5, OCR H446 2.3.1 (b) to (f)
| Board | Topic: Algorithms |
|---|---|
| AQA 7517 | 4.3.2, 4.3.4 to 4.3.6, 4.4.1 (problem solving) |
| OCR H446 | 2.1, 2.2.2, 2.3.1 |
| Higher C816 76 | Software design and development: standard algorithms (linear search, find maximum and minimum, count occurrences) |
Bubble sort
Go through the list comparing each neighbouring pair and swap them if they are in the wrong order. After one pass the largest item has "bubbled" to the end. Repeat on the rest. An improved version stops early if a pass makes no swaps, so an already sorted list takes just one pass.
Insertion sort
Treat the first item as a sorted list of one. Take each following item and slide it left past every larger item until it sits in the right place in the sorted part. It is quick for small lists and lists that are nearly sorted.
Merge sort and quick sort
- Merge sort: split the list in half again and again until each part has one item, then merge pairs of sorted lists by repeatedly taking the smaller front item. It needs extra memory for the merged lists.
- Quick sort (OCR): choose a pivot, move smaller items to its left and larger items to its right, then sort each side the same way. It sorts in place, but a poor pivot, such as the first item of an already sorted list, gives O(n²).
Comparing them
| Algorithm | Best | Average | Worst | Extra memory |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) for recursion |
How many comparisons does one full pass of bubble sort make on 8 items?
Show the answer
7 (one fewer than the number of items).
Part 2 of 3: See it worked
Worked examples
Example 1
Show the first pass of a bubble sort on 5, 1, 4, 2, 8.
- Compare 5 and 1: swap, giving 1, 5, 4, 2, 8
- Compare 5 and 4: swap, giving 1, 4, 5, 2, 8
- Compare 5 and 2: swap, giving 1, 4, 2, 5, 8
- Compare 5 and 8: no swap
Answer: 1, 4, 2, 5, 8 after the first pass.
Example 2
Use merge sort on 38, 27, 43, 3.
- Split: [38, 27] and [43, 3], then [38] [27] [43] [3]
- Merge pairs: [27, 38] and [3, 43]
- Merge: compare 27 and 3, take 3; compare 27 and 43, take 27; compare 38 and 43, take 38; then 43
Answer: 3, 27, 38, 43.
Common mistakes
- Saying bubble sort is always O(n²). With the early-exit check, a sorted list takes O(n).
- In merge sort, merging without comparing the front items of both lists.
- Saying quick sort is always faster than merge sort. Its worst case is O(n²).
- Forgetting that merge sort needs extra memory.
Which of these sorts is best for a list that is already almost in order: insertion or merge?
Show the answer
Insertion sort, which approaches O(n) on nearly sorted data.
Part 3 of 3: Test yourself
Check yourself
Answer each one in your head or on paper first, then open it to check.
How many comparisons does one full pass of bubble sort make on 8 items?
7 (one fewer than the number of items).
Which of these sorts is best for a list that is already almost in order: insertion or merge?
Insertion sort, which approaches O(n) on nearly sorted data.
What is the time complexity of merge sort in the worst case?
O(n log n).
Jobs that use this
- Software developer (s'ouvre dans un nouvel onglet)
- Data scientist (s'ouvre dans un nouvel onglet)
- Computer games developer (s'ouvre dans un nouvel onglet)
Each link opens the job profile on the National Careers Service (England). In the rest of the UK: My World of Work (Scotland), Careers Wales, nidirect careers (Northern Ireland).
Ces fiches sont en anglais car elles suivent les programmes d'examen britanniques.
Full lessons and marked practice for this course are coming soon to Brainlag Learn. See courses