Understand the bubble sort and merge sort algorithms, how each orders a list, their time complexity, and the trade-off between them.

What this dot point is asking

AQA wants you to describe how bubble sort and merge sort work, give the time complexity of each, trace a pass, and explain the trade-off between the simple bubble sort and the more efficient merge sort.

Bubble sort

FOR pass = 1 TO n - 1
  swapped = False
  FOR i = 0 TO n - 1 - pass
    IF list[i] > list[i + 1] THEN
      swap(list[i], list[i + 1])
      swapped = True
  IF NOT swapped THEN break   # already sorted

Bubble sort has worst- and average-case time complexity $O(n^2)$ because of the nested loops: roughly $n$ passes each doing up to $n$ comparisons. The best case, on an already sorted list with the early-exit flag, is $O(n)$ because a single clean pass detects that no swaps were needed. It sorts in place (no extra memory beyond a temporary swap variable), which is its main appeal, but it is impractical for large lists.

Merge sort

mergeSort(list):
  IF length <= 1 THEN RETURN list
  split into left and right halves
  left = mergeSort(left)
  right = mergeSort(right)
  RETURN merge(left, right)   # combine in sorted order

The merge step is where the ordering happens: two already-sorted sublists are combined by repeatedly taking the smaller of the two front items, which is why each merge level is linear in the number of items.

The trade-off

Bubble sort is easy to understand and uses no extra memory, but its $O(n^2)$ growth makes it too slow for large data. Merge sort is harder to code and uses additional memory, but its $O(n \log n)$ growth makes it the right choice for large lists. This illustrates the general trade-off between simplicity and efficiency, and the related trade-off between time and space.

To see the gap in practice, consider sorting a list of one million items. Bubble sort performs on the order of $n^2 = 10^{12}$ comparisons, which is around a trillion operations and would take an unacceptably long time. Merge sort performs on the order of $n \log n \approx 10^6 \times 20 = 2 \times 10^7$ operations, around twenty million, which a modern processor handles in a fraction of a second. The difference is not a constant factor that faster hardware can overcome; it grows with the data, which is exactly the point Big-O is making.

There is also a difference in adaptiveness. Bubble sort with the early-exit flag is adaptive: on a list that is already sorted it makes a single $O(n)$ pass and stops, which is why it is occasionally used to detect whether a small list is in order. Merge sort always does the full $O(n \log n)$ work regardless of the starting arrangement, because it splits and merges the whole list every time. Merge sort is also a stable sort, meaning equal elements keep their original relative order, a property that matters when sorting records by one field while preserving an earlier ordering on another. These finer points (adaptiveness and stability) are the kind of detail that distinguishes a top-band answer from a bare recall of the two complexities.