SingaporeComputer ScienceSyllabus dot point

How do divide-and-conquer sorts achieve O(n log n), and how do merge sort and quicksort differ?

Explain and trace merge sort and quicksort as divide-and-conquer algorithms, analyse their complexity, and compare their trade-offs

A focused answer to the H2 Computing outcome on efficient sorts. Merge sort and quicksort as divide-and-conquer, their O(n log n) behaviour, quicksort's worst case, and the trade-off between stability, memory and speed.

Generated by Claude Opus 4.89 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to explain and trace merge sort and quicksort as divide-and-conquer algorithms, analyse their complexity, and compare their trade-offs. The central idea is that splitting a problem into halves and combining the results turns an $O(n^2)$ sort into $O(n \log n)$ - and that merge sort and quicksort make different choices about where the hard work happens.

The answer

Divide and conquer

Both sorts follow the same template: divide the list into smaller parts, conquer by sorting each part recursively, and combine the results. The base case is a list of 0 or 1 element, which is already sorted.

Merge sort

Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves:

def merge_sort(data):
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = merge_sort(data[:mid])
    right = merge_sort(data[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

The list is halved $\log_2 n$ times, and merging at each level costs $O(n)$ in total, so the time is $O(n \log n)$ in all cases. It needs $O(n)$ extra space for the merged output and is stable (equal elements keep their order).

Quicksort

Quicksort picks a pivot and partitions the list so smaller elements go left and larger go right; the pivot lands in its final place. It then recurses on each side:

def quicksort(data, low, high):
    if low < high:
        p = partition(data, low, high)
        quicksort(data, low, p - 1)
        quicksort(data, p + 1, high)

On average the partitions are balanced, giving $O(n \log n)$ . But if the pivot is repeatedly the smallest or largest element (for example a sorted list with a naive pivot), partitions are maximally unbalanced and it degrades to $O(n^2)$ . Quicksort sorts in place ( $O(\log n)$ extra space).

Comparing the trade-offs

Property	Merge sort	Quicksort
Average time	$O(n \log n)$	$O(n \log n)$
Worst time	$O(n \log n)$	$O(n^2)$
Extra space	$O(n)$	$O(\log n)$
Stable	Yes	Not usually

Merge sort guarantees $O(n \log n)$ and stability but uses more memory; quicksort is usually faster in practice and in place, but has a quadratic worst case mitigated by good pivot choice.

Worked example

Show how quicksort partitions $[7, 2, 9, 4, 3]$ using the last element ( $3$ ) as the pivot.

Step 1: Choose the pivot

The pivot is the last element, $3$ . We want all values $\le 3$ before it and all $> 3$ after it.

Step 2: Scan and place smaller elements left

Walk the other elements $[7, 2, 9, 4]$ . Only $2$ is $\le 3$ , so it goes to the front; $7, 9, 4$ are all greater and stay to the right.

Step 3: Put the pivot in its final position

After partitioning, the arrangement is $[2,\ 3,\ 7, 9, 4]$ - the pivot $3$ sits between the smaller group $\{2\}$ and the larger group $\{7, 9, 4\}$ , in its final sorted position (index 1).

Step 4: Recurse on each side

Recurse on the left partition $[2]$ (already sorted) and the right partition $[7, 9, 4]$ . Sorting the right partition the same way yields $[4, 7, 9]$ , giving the final list $[2, 3, 4, 7, 9]$ .

Examples in context

Example 1. Sorting external data. When sorting a dataset too large to fit in memory, merge sort's predictable merging of sorted chunks (an external merge sort) is the natural fit, because it streams data and combines sorted runs without random access - the same merge step scaled up.

Example 2. Library sort functions. Many standard libraries use a hybrid: quicksort or a quicksort variant for speed and in-place operation, switching to insertion sort for small partitions and sometimes to a guaranteed $O(n \log n)$ method to dodge quicksort's worst case. The choice reflects exactly the trade-offs in the table above.

Try this

Q1. State the time complexity of merge sort in the worst case and explain why it is the same as its average case. [2 marks]

Cue. $O(n \log n)$ - it always halves the list ( $\log n$ levels) and always does $O(n)$ merging per level, regardless of input.

Q2. What input causes quicksort's $O(n^2)$ worst case with a first-element pivot? [1 mark]

Cue. An already-sorted (or reverse-sorted) list, which makes every partition maximally unbalanced.

Q3. Give one advantage of merge sort over quicksort. [1 mark]

Cue. It guarantees $O(n \log n)$ in all cases and is stable (equal elements keep their relative order).

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original6 marks(a) Explain how merge sort uses divide and conquer to sort a list. (b) State its time complexity and explain why the

\log n

factor appears. (c) Trace the merge step that combines the two sorted halves

[2, 5, 8]

and

[1, 6]

Show worked answer →

(a) Merge sort splits the list into two halves, recursively sorts each half, then merges the two sorted halves into one sorted list. The base case is a list of length 0 or 1, which is already sorted.

(b) Time complexity is $O(n \\log n)$ . The list is halved $\\log_2 n$ times (the depth of recursion), and at each level the total merging work across all sublists is $O(n)$ , giving $n \\times \\log n$ .

[2,5,8] [1,6] -> take 1 -> [1]
[2,5,8] [6]   -> take 2 -> [1,2]
[5,8]   [6]   -> take 5 -> [1,2,5]
[8]     [6]   -> take 6 -> [1,2,5,6]
[8]     []    -> take 8 -> [1,2,5,6,8]

Markers reward the split-sort-merge description, $O(n \\log n)$ with the halving-depth-times-linear-merge reason, and a correct merge producing $[1, 2, 5, 6, 8]$ .

Original5 marks(a) Describe how quicksort partitions a list around a pivot. (b) State quicksort's average and worst-case time complexity, and explain what input causes the worst case. (c) Give one advantage of quicksort over merge sort.

Show worked answer →

(a) Quicksort chooses a pivot element and partitions the list so that everything smaller than the pivot is to its left and everything larger is to its right. The pivot is then in its final position; quicksort recurses on the left and right partitions.

(b) Average case $O(n \\log n)$ ; worst case $O(n^2)$ . The worst case occurs when the pivot is consistently the smallest or largest element (for example, an already-sorted list with a naive first-element pivot), so partitions are maximally unbalanced - one side empty, the other nearly full - giving $n$ levels of $O(n)$ work.

(c) Quicksort sorts in place, needing only $O(\\log n)$ extra space for recursion, whereas merge sort needs $O(n)$ extra space for the merge. So quicksort is more memory-efficient.

Markers reward the pivot-and-partition description, the average $O(n \\log n)$ and worst $O(n^2)$ with the unbalanced-partition cause, and a valid advantage such as in-place sorting.