Merge Sort & Quick Sort: Divide-and-Conquer Sorting (OCR A-Level CS 2.3.1)

Free Merge Quick Sort revision resources (OCR A-Level Computer Science, 2.3.1)

We’ve made exam-style practice for this exact topic, free to download: Merge Quick Sort question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.

Bubble and insertion sort are simple but slow. Merge sort and quick sort are the fast ones — both divide-and-conquer algorithms that run in O(n log n) and scale beautifully to large lists. Spec point 2.3.1(f) expects you to know how each works, trace them, and compare them (including with the O(n²) sorts). Let's build both up.

Merge sort

Merge sort is a classic divide-and-conquer algorithm:

1. Divide — split the list in half, again and again, until every piece is a single item (a list of one is already sorted).

2. Conquer (merge) — repeatedly merge pairs of sorted sub-lists back together, each time comparing the fronts and taking the smaller, until one sorted list remains.

Tracing [38, 27, 43, 3] is the easiest way to see it:

• Split → [38, 27] and [43, 3] → then singles [38] [27] [43] [3].

• Merge [38]+[27] → [27, 38]; merge [43]+[3] → [3, 43].

• Merge [27, 38]+[3, 43] → [3, 27, 38, 43].

Merge sort is O(n log n) — there are log n levels of splitting, and each level does O(n) work merging. Its drawback: it needs extra memory to hold the sub-lists (it's not in place).

Quick sort

Quick sort is also divide-and-conquer, but it splits by value using a pivot:

1. Choose a pivot (e.g. the first or last item).

2. Partition — put all items smaller than the pivot to its left and all items larger to its right. The pivot is now in its final position.

3. Recurse — quick sort the left part and the right part the same way.

Tracing [7, 2, 1, 6, 8, 5, 3, 4] with the last item (4) as pivot:

• Partition around 4 → smaller [2, 1, 3], pivot 4, larger [7, 6, 8, 5].

• Quick sort [2, 1, 3] (pivot 3 → [2,1], 3) → [1, 2, 3]; quick sort [7, 6, 8, 5] → [5, 6, 7, 8].

• Result: [1, 2, 3, 4, 5, 6, 7, 8].

Quick sort is O(n log n) on average and can sort in place (less memory than merge sort), but its worst case is O(n²) if the pivot is consistently poor (e.g. an already-sorted list with the first element as pivot).

Comparing the sorts

Both merge and quick sort massively outperform the O(n²) sorts on large data. Merge sort guarantees O(n log n) but uses more memory; quick sort is usually fastest in practice and memory-light, but has a worst case if pivots are poor.

Worked example: why these are "divide and conquer"

Both split a problem into smaller sub-problems of the same kind and combine the results — the textbook definition of divide and conquer. Merge sort divides by position (halves) and combines by merging; quick sort divides by value (around a pivot) and combines simply by concatenation (left + pivot + right). That repeated halving is why both reach O(n log n) rather than O(n²).

Common exam mistakes

• Confusing the split. Merge sort splits by position (in half); quick sort splits by value (around a pivot).

• Forgetting merge sort's memory cost. It is not in place — it needs extra lists.

• Missing quick sort's worst case. With consistently poor pivots it degrades to O(n²).

• Wrong complexity. Both are O(n log n) typically — far better than the O(n²) simple sorts.

• Trace gaps. Show the split tree (merge) or the partitions around each pivot (quick).

Quick recap

• Merge sort: divide the list into single items, then merge sorted sub-lists back together — O(n log n), but not in place (extra memory).

• Quick sort: choose a pivot, partition into smaller/larger, recurse on each part — O(n log n) average, can be in place, but O(n²) worst case with poor pivots.

• Both are divide and conquer and scale far better than bubble/insertion sort (O(n²)) on large lists.

• Merge sort = guaranteed O(n log n), more memory; quick sort = usually fastest, memory-light, risky worst case.

• Trace merge sort with a split/merge tree; quick sort by the partitions around each pivot.

Frequently asked questions

How does a merge sort work? A merge sort repeatedly splits the list in half until every piece is a single item, which is already sorted. It then merges pairs of sorted sub-lists back together, each time comparing the fronts of the two and taking the smaller, until one fully sorted list remains. It is a divide-and-conquer algorithm.

How does a quick sort work? A quick sort chooses a pivot value and partitions the list so that all items smaller than the pivot are on its left and all larger items are on its right, which places the pivot in its final position. It then recursively quick sorts the left and right parts in the same way until the whole list is sorted.

What are the time complexities of merge sort and quick sort? Both run in O(n log n) on average, because they repeatedly halve the problem (log n levels) doing O(n) work per level. Merge sort is O(n log n) in the worst case too, while quick sort can degrade to O(n²) in the worst case if the pivot is consistently poorly chosen.

What is the difference between merge sort and quick sort? Merge sort divides the list by position into halves and combines the results by merging, and it needs extra memory because it is not in place. Quick sort divides by value around a pivot and combines by concatenation, can sort in place using little extra memory, but has an O(n²) worst case with poor pivots.

Why are merge sort and quick sort faster than bubble sort? Bubble sort is O(n²), so its work grows with the square of the list size, whereas merge and quick sort are O(n log n) because they repeatedly halve the problem. For large lists this difference is enormous — for a million items the O(n log n) sorts do roughly twenty million operations versus a million-million for an O(n²) sort.

Why is merge sort described as divide and conquer? Merge sort is divide and conquer because it repeatedly divides the list into smaller sub-lists of the same kind, sorts those, and then combines (merges) the results into the full sorted list. Quick sort is also divide and conquer, dividing the list by value around a pivot and combining the sorted parts.