Merge Sort and Quick Sort

Merge sort and quick sort are efficient comparison-based sorting algorithms with average-case time complexity of O(n log n), making them vastly superior to the O(n²) simple sorts for large datasets. Both use the divide and conquer paradigm. At A-Level, you must understand how each algorithm works, be able to trace them, and compare their complexities and trade-offs.

---

Merge Sort

How It Works

Merge sort uses a divide and conquer strategy:

1. Divide: Recursively split the list into halves until each sub-list contains one element.
2. Conquer (Merge): Merge pairs of sub-lists back together in sorted order.

A list of one element is inherently sorted, so the "base case" of the recursion is a single-element list.

Pseudocode

FUNCTION mergeSort(arr)
    IF LENGTH(arr) <= 1 THEN
        RETURN arr
    END IF
    mid = LENGTH(arr) DIV 2
    left = mergeSort(arr[0..mid-1])
    right = mergeSort(arr[mid..end])
    RETURN merge(left, right)
END FUNCTION

FUNCTION merge(left, right)
    result = []
    i = 0
    j = 0
    WHILE i < LENGTH(left) AND j < LENGTH(right)
        IF left[i] <= right[j] THEN
            APPEND left[i] TO result
            i = i + 1
        ELSE
            APPEND right[j] TO result
            j = j + 1
        END IF
    END WHILE
    APPEND remaining elements of left to result
    APPEND remaining elements of right to result
    RETURN result
END FUNCTION

Trace Example

Sorting [38, 27, 43, 3, 9, 82, 10]:

Split phase:

[38, 27, 43, 3, 9, 82, 10]
       /                \
[38, 27, 43]        [3, 9, 82, 10]
   /      \            /         \
[38]   [27, 43]    [3, 9]    [82, 10]
        /    \      /   \      /    \
      [27]  [43]  [3]  [9]  [82]  [10]

Merge phase:

[27]  [43]  →  [27, 43]
[38]  [27, 43]  →  [27, 38, 43]
[3]  [9]  →  [3, 9]
[82]  [10]  →  [10, 82]
[3, 9]  [10, 82]  →  [3, 9, 10, 82]
[27, 38, 43]  [3, 9, 10, 82]  →  [3, 9, 10, 27, 38, 43, 82]

Complexity

Case	Time	Space
Best	O(n log n)	O(n)
Worst	O(n log n)	O(n)
Average	O(n log n)	O(n)

Why O(n log n)? The list is divided in half log₂(n) times (the split phase). At each level of recursion, merging takes O(n) comparisons across all sub-lists. Therefore: O(n) x O(log n) = O(n log n).

Why O(n) space? Merge sort creates new arrays during the merge phase. At any point, the total extra memory needed is proportional to n.

---

Quick Sort

How It Works

Quick sort also uses divide and conquer, but instead of splitting in the middle, it selects a pivot element and partitions the list into:

• Elements less than the pivot (left partition)
• Elements greater than the pivot (right partition)

The pivot is then in its final sorted position. The algorithm recursively sorts the left and right partitions.

Pseudocode