Sorting algorithms

What you need to know

• ✓Bubble sort steps through a list, compares adjacent pairs of items, and swaps them if they are in the wrong order.
• ✓In bubble sort, each full pass moves (bubbles) the highest unsorted value to its correct final position at the end of the list.
• ✓Bubble sort requires a full pass with zero swaps to confirm the list is completely sorted.
• ✓Bubble sort is memory-efficient because it sorts in place (it does not require additional memory to store temporary sublists).
• ✓Merge sort is a divide-and-conquer algorithm: it repeatedly splits the list into halves until each sublist contains only one item, then merges adjacent sublists back together in sorted order.
• ✓Merge sort is significantly more time-efficient than bubble sort on large datasets, but it requires additional memory space to hold the divided lists during merging.

What you don’t need

• Insertion sort, quicksort, and selection sort — only bubble sort and merge sort are tested under AQA 8525.
• Formal Big-O notation (e.g. O(n²) or O(n log n)).
• Writing full recursive merge sort implementations in program code.

Worked examples

1. Perform the first pass of a bubble sort on the list [5, 2, 8, 1, 4] to sort into ascending order.

   1. Compare 5 and 2: 5 > 2, so swap -> [2, 5, 8, 1, 4].
   2. Compare 5 and 8: 5 < 8, no swap -> [2, 5, 8, 1, 4].
   3. Compare 8 and 1: 8 > 1, so swap -> [2, 5, 1, 8, 4].
   4. Compare 8 and 4: 8 > 4, so swap -> [2, 5, 1, 4, 8].

   Answer: After pass 1, the list is [2, 5, 1, 4, 8]. The largest number (8) has bubbled to the final position.

2. Explain one advantage of merge sort over bubble sort, and one advantage of bubble sort over merge sort. (2 marks)

   Answer: Advantage of merge sort: It is far faster / more time-efficient on large lists. Advantage of bubble sort: It uses less memory because it sorts the items in place without needing extra space for temporary sublists.

Common mistakes

• ✕Stopping bubble sort as soon as the numbers look sorted to human eyes without completing a full swapless verification pass.
• ✕Forgetting to compare items during the merge phase of merge sort — items must be compared as they are reassembled, not merely concatenated.
• ✕Claiming bubble sort is faster on large lists because it is simpler to code — bubble sort becomes extremely slow as list size grows.
• ✕Mentioning insertion sort — insertion sort is on OCR's specification, but NOT on AQA 8525.