A-level Computer Science revision · Data structures and algorithms

Merge sort and quicksort

The idea

Merge sort is divide and conquer: split the list in half until single items remain, then merge sorted lists. It is O(n log n) but needs extra memory. Quicksort picks a pivot, partitions items into smaller and larger, then sorts each part recursively: O(n log n) on average but O(n²) in the worst case.

  1. Merge sort: split, then merge pairs in order.
  2. Quicksort: pivot, partition, recurse.
  3. Compare time and space.

Watch out Quicksort's worst case is O(n²), for example when the pivot is always the smallest item.

See it worked

Worked example

Merge [3, 8] and [1, 9].

  1. Compare fronts: 1 < 3, take 1.
  2. 3 < 9, take 3; 8 < 9, take 8.
  3. Then 9: [1, 3, 8, 9].

Answer [1, 3, 8, 9]

Your turn

Question 11 mark

What is the time complexity of merge sort?

Choose one
Question 21 mark

What is a disadvantage of merge sort compared with quicksort?

Choose one
Question 32 marks

Explain how quicksort uses a pivot.

Write your answer, then see a model answer
  1. Describe the partition.
  2. Describe the recursion.

Answer Items smaller than the pivot are placed before it and larger after it, so the pivot is in its final place; the two sides are then sorted recursively.

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms