Merge [3, 8] and [1, 9].
- Compare fronts: 1 < 3, take 1.
- 3 < 9, take 3; 8 < 9, take 8.
- Then 9: [1, 3, 8, 9].
Answer [1, 3, 8, 9]
A-level Computer Science revision · Data structures and algorithms
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.
Watch out Quicksort's worst case is O(n²), for example when the pivot is always the smallest item.
Merge [3, 8] and [1, 9].
Answer [1, 3, 8, 9]
What is the time complexity of merge sort?
What is a disadvantage of merge sort compared with quicksort?
Explain how quicksort uses a pivot.
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
£119 once
Price rises to £199 on 1 January. Save £80 by joining before then.
At least 12 months of access
No VAT is charged.