Merge sort — AQA A-Level Computer Science
Merge sort is an efficient, divide-and-conquer sorting algorithm that recursively splits an array into individual sublists before systematically merging them in sorted order. It guarantees an optimal time complexity of O(n log n) in all cases, though it incurs an O(n) auxiliary space overhead.
Merge sort explained
Merge sort is a divide-and-conquer algorithm.
Read the full explanation
It repeatedly splits a list into two halves until each part holds a single item, then merges sorted pairs of sublists back together in order. To trace merge sort, a learner follows the splits and then the merges step by step, recording how the list looks after each merge, so that the order of operations is clear. To analyse its time complexity, the learner considers two parts of the work: the number of times the list can be halved, which is about log₂n levels for n items, and the work done at each level, where merging touches every item once, giving about n operations per level. Multiplying these gives roughly n log₂n comparisons in the worst case, which is much more efficient than bubble sort's n² growth for large lists. Learners should be able to explain each step of this reasoning, not simply recall the final expression.
Your focus
- Be able to trace and analyse the time complexity of the merge sort algorithm.
Which command word is this?
Show every intermediate state of the data structure. For merge sort, clearly delineate each split level and each recombined, sorted sublist.
Merge sort exam tips
Topic Overview
Merge sort is a fundamental algorithm in AQA A-Level Computer Science, exemplifying the divide-and-conquer algorithmic design paradigm. It operates by recursively decomposing an unordered dataset into sublists of size one, then repeatedly merging adjacent sorted sublists using pointer comparisons until a single unified sorted sequence remains.
Understanding merge sort is vital for evaluating algorithm efficiency, recursion, and space-time trade-offs. It serves as a benchmark O(n log n) sorting algorithm, contrasting sharply with quadratic algorithms like bubble sort and insertion sort, while providing students with practical insight into recursion stacks and memory allocation.
Key Concepts
- →Divide-and-conquer paradigm: The problem is split into independent subproblems (divide), solved recursively down to base cases of length 1 (conquer), and reconstructed into a solved whole (combine).
- →Time complexity consistency: Best, average, and worst-case time complexities are all strictly O(n log n) because the array is always split evenly into log2(n) recursive levels.
- →Auxiliary space complexity: Standard array-based merge sort requires O(n) temporary storage space to hold elements during the merge process.
- →Stable sorting property: Preserves the relative order of duplicate elements because ties during the merge step are resolved in favor of the left sublist.
Marking Points
- Traces the splitting of the list into halves until single items remain, then the merging back in sorted order.
- Explains that the list can be halved about log₂n times for n items.
- Explains that each merge level processes about n items, so the work per level is proportional to n.
- Combines the number of levels and the work per level to reach roughly n log₂n time complexity.
- Compares this with the n² growth of bubble sort to show why merge sort scales better.
Examiner Tips
- 💡Write out the splits and merges for a small list such as eight items before attempting an analysis question.
- 💡State the number of levels and the work per level separately, then combine them.
- 💡Use the expression n log₂n when comparing merge sort with bubble sort.
- 💡When drawing a trace diagram, explicitly show sublists down to single-item arrays (length 1) to gain full method marks for the division phase.
- 💡Memorize the exact Big-O complexities: Best O(n log n), Average O(n log n), Worst O(n log n), and Space O(n). Examiners frequently test the space complexity.
- 💡In comparison questions, always pair algorithmic advantages (e.g. predictable O(n log n) time) with trade-offs (e.g. higher memory overhead than quicksort or bubble sort).
Common Mistakes
- States that merge sort is n² because it uses nested loops; merge sort's time comes from halving the list, giving n log₂n overall.
- Forgets the logarithm when describing the number of levels, treating the splitting as linear; correct it by halving the list each time, which gives log₂n levels.
- Traces the merges without showing the sorted sublists after each step; record the intermediate lists to make the trace clear.
- Believing merge sort sorts during the division phase; division merely decomposes the array until base cases are met, while all ordering occurs strictly during merging.
- Assuming merge sort has an O(n) best-case time complexity like insertion sort; standard merge sort performs the full split and merge operations regardless of whether the list is already sorted.
- Overlooking the auxiliary space requirement by assuming the algorithm sorts in-place within the original array.
Revision Plan
- 1Day 1: Master the divide-and-conquer logic and practice manual trace diagrams with odd and even length arrays.
- 2Day 2: Write out and annotate merge sort pseudocode, paying close attention to base cases and recursive return values.
- 3Day 3: Derive time and space complexities mathematically (depth of log2(n) times n work) and contrast with quicksort and bubble sort.
- 4Day 4: Attempt past AQA exam questions focusing on 4-mark tracing questions and 6-mark comparative essays.
Exam Question Types
- 📋Tracing diagrams: Illustrate the recursive splitting and merging of a given list of numbers or characters.
- 📋Complexity analysis: State and justify the time and space complexity in best, average, and worst scenarios.
- 📋Algorithm comparison: 6-to-9 mark questions comparing merge sort, quicksort, and bubble sort in terms of time, memory, and stability.
Command Word Expectations (AQA)
Show every intermediate state of the data structure. For merge sort, clearly delineate each split level and each recombined, sorted sublist.
Give reasons for how or why a mechanism works, using precise technical terminology such as recursion, base case, divide-and-conquer, and linear merge.
Identify both similarities and differences between two algorithms across specific metrics: best/worst time complexity, space complexity, and stability.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: An array contains the following seven integers: [38, 27, 43, 3, 9, 82, 10]. Show the step-by-step trace of how merge sort divides and merges these elements into ascending order.
- 1.Step 1: Divide array recursively down to base cases. Split 1: Left = [38, 27, 43], Right = [3, 9, 82, 10].
- 2.Step 2: Subdivide Left [38, 27, 43] into [38] and [27, 43]; subdivide [27, 43] into [27] and [43]. Subdivide Right [3, 9, 82, 10] into [3, 9] and [82, 10]; subdivide [3, 9] into [3] and [9], and [82, 10] into [82] and [10]. All sublists now have length 1.
- 3.Step 3: Begin merging sublists by comparing front elements. Left side merges: [27] and [43] merge to [27, 43]. Then [38] and [27, 43] merge to [27, 38, 43].
- 4.Step 4: Right side merges: [3] and [9] merge to [3, 9]. [82] and [10] merge to [10, 82]. Then [3, 9] and [10, 82] merge to [3, 9, 10, 82].
- 5.Step 5: Final merge of two sorted halves: Compare head elements of [27, 38, 43] and [3, 9, 10, 82]. 3 < 27 -> [3]; 9 < 27 -> [3, 9]; 10 < 27 -> [3, 9, 10]; 27 < 82 -> [3, 9, 10, 27]; 38 < 82 -> [3, 9, 10, 27, 38]; 43 < 82 -> [3, 9, 10, 27, 38, 43]; append remaining [82].
Question: Explain why merge sort has a worst-case time complexity of O(n log n) while bubble sort has a worst-case time complexity of O(n^2). Refer to operations performed at each stage.
- 1.Step 1: Define the division depth of merge sort. Halving an array of size n creates a recursion tree of height log2(n) levels.
- 2.Step 2: Define work per level for merge sort. At each level of the tree, merging sublists requires comparing and combining all n elements, taking linear time O(n). Multiplying n by log2(n) levels gives O(n log n) worst-case time.
- 3.Step 3: Define the structure of bubble sort. Bubble sort uses nested loops. In the worst case (reverse order), the outer loop runs (n - 1) times and the inner loop performs (n - i) adjacent comparisons.
- 4.Step 4: Quantify the total operations for bubble sort. Total comparisons equal (n(n - 1))/2, which expands to O(n^2).
- 5.Step 5: Compare efficiency. For large n, O(n log n) scales substantially better than O(n^2) because logarithmic height avoids pairwise quadratic comparisons.