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