Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1: Master the divide-and-conquer logic and practice manual trace diagrams with odd and even length arrays.
    2. 2Day 2: Write out and annotate merge sort pseudocode, paying close attention to base cases and recursive return values.
    3. 3Day 3: Derive time and space complexities mathematically (depth of log2(n) times n work) and contrast with quicksort and bubble sort.
    4. 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)
    Trace

    Show every intermediate state of the data structure. For merge sort, clearly delineate each split level and each recombined, sorted sublist.

    Explain

    Give reasons for how or why a mechanism works, using precise technical terminology such as recursion, base case, divide-and-conquer, and linear merge.

    Compare

    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)
    Pitfall: Confusing the time complexity with space complexity, or claiming merge sort executes in-place.
    ❌ Weak Answer (Loses Marks):Merge sort is fast with O(n log n) complexity and it sorts the list without needing extra memory because it uses pointers.
    Example improved answer:Merge sort achieves a time complexity of O(n log n) across best, average, and worst cases due to log n recursive division levels and O(n) work per merge level. However, its space complexity is O(n) because it requires auxiliary memory buffers to store elements during the merge phase.
    Examiner Tip: Always distinguish between time complexity and auxiliary space complexity. State explicitly that merge sort is not an in-place sort for standard array implementations.
    Pitfall: Failing to demonstrate the tree structure or step-by-step merge process when asked to trace merge sort on an odd-numbered list.
    ❌ Weak Answer (Loses Marks):The list [7, 2, 9, 1, 5] splits into [7, 2] and [9, 1, 5], then sorts to [1, 2, 5, 7, 9].
    Example improved answer:Divide: [7, 2, 9, 1, 5] splits into [7, 2] and [9, 1, 5]. [7, 2] splits into [7] and [2]. [9, 1, 5] splits into [9] and [1, 5], which further divides into [1] and [5]. Base case reached with sublists of length 1. Merge: [7] and [2] merge to [2, 7]. [1] and [5] merge to [1, 5]. [9] and [1, 5] merge to [1, 5, 9]. Finally, [2, 7] and [1, 5, 9] merge by comparing front pointers to produce [1, 2, 5, 7, 9].
    Examiner Tip: Show every level of division until single-element sublists are obtained before drawing the merge steps. Mark schemes award marks for intermediate sublists.
    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. 1.Step 1: Divide array recursively down to base cases. Split 1: Left = [38, 27, 43], Right = [3, 9, 82, 10].
    2. 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. 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. 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. 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].
    Final Answer: Fully sorted array: [3, 9, 10, 27, 38, 43, 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. 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. 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. 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. 4.Step 4: Quantify the total operations for bubble sort. Total comparisons equal (n(n - 1))/2, which expands to O(n^2).
    5. 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.
    Final Answer: Merge sort divides the problem into log2(n) levels requiring O(n) comparisons per level (total O(n log n)), whereas bubble sort relies on nested iterations performing approximately n^2/2 comparisons (total O(n^2)).
    Active Recall Memory Test
    What is the worst-case time complexity of merge sort, and why does it occur?
    Key Fact: O(n log n). It occurs in all cases because the list is always divided into log2(n) levels and n comparisons are made across each level.
    What is the auxiliary space complexity of standard merge sort?
    Key Fact: O(n), due to temporary arrays needed to merge sublists.
    What algorithmic paradigm does merge sort use?
    Key Fact: Divide and conquer.
    At what point does the recursive division of a sublist terminate in merge sort?
    Key Fact: When the sublist contains exactly one element (length <= 1), which forms the base case.
    Frequently Asked Questions
    Why is merge sort always O(n log n) even if the list is already sorted?
    Standard merge sort does not inspect elements before splitting. It unconditionally divides the list in half until single-item sublists remain, creating log2(n) levels. During the merge step, it must still compare elements to reconstruct the sorted array, meaning the full complement of operations is executed regardless of initial list order.
    Is merge sort faster than quicksort?
    Merge sort has a superior worst-case time complexity of O(n log n) compared to quicksort's worst-case O(n^2). However, in practice, quicksort is often faster on average due to lower constant factors, better cache locality, and an in-place space complexity of O(log n) versus merge sort's O(n) auxiliary memory requirement.
    What does it mean that merge sort is a stable sort?
    A sorting algorithm is stable if it preserves the original relative order of records that have equal keys. In merge sort, when two compared elements are equal, the algorithm by default selects the element from the left sublist first, thereby retaining its initial position relative to the identical element from the right sublist.
    How do you trace merge sort if an array has an odd number of elements?
    When an array length cannot be split evenly, adopt integer division (floor division). For example, a list of 5 elements is split into sublists of size 2 and size 3. As long as you consistently apply the same splitting convention (e.g., left side gets floor(n/2) items), your trace will remain completely valid and receive full marks.