Merge Sort and Quick Sort — Divide-and-Conquer Sorting

Build the mental model

Both merge sort and quicksort beat simple sorts by using divide-and-conquer, but they split the work differently, and that difference is the whole trade-off. Merge sort splits the array blindly down the middle, recursively sorts each half, then merges the two sorted halves by repeatedly taking the smaller front element — this merge step is what preserves original order among equal elements, making merge sort stable. Its O(n log n) bound holds unconditionally, but merging needs a second array, so it costs O(n) extra memory. Quicksort instead picks a pivot and partitions the array so smaller elements land left, larger ones right, then recurses on each side — no extra array needed, so it sorts in place. Its average case is O(n log n), but if the pivot choice is consistently bad (a naive 'always pick the first element' pivot on already-sorted input), partitions become lopsided and it degrades to O(n²). This is why production quicksort implementations randomize or median-of-three the pivot — the algorithm's real-world speed depends entirely on avoiding that worst case.

Connect it to a real scenario

When the Tutorial Platform sorts a large batch of lessons — say, re-ranking an entire topic's lesson list after an editorial update — the algorithm choice matters. If tie-breaking order (originally by publish date) must survive the sort, merge sort's stability guarantee makes it the safe default despite the extra memory. But for a one-off in-place sort of a smaller, transient list — like sorting an array of view-counts to compute a trending snapshot — quicksort's in-place, no-extra-allocation behavior is the better fit, as long as the input isn't adversarially ordered. Recognizing which guarantee the situation actually needs, rather than always reaching for 'the fast one,' is the real skill here.

Merge sort guarantees O(n log n) and is stable, but requires O(n) extra memory.
Quicksort is average-case O(n log n) and in-place, but can degrade to worst-case O(n²) with a poor pivot choice.
Production quicksort implementations randomize or median-of-three the pivot to avoid the worst case.

Try the working example

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[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]:  # <= keeps merge sort stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

You should see

Prints the sorted list [3, 9, 10, 27, 38, 43, 82].

5-minute try-it

Change the `<=` in merge to `<` and sort a list of tuples with equal keys like (a, 'x') — observe how the output order changes and why.

One important caution

Implementing quicksort with an always-first-element pivot and running it on already-sorted or reverse-sorted input — this instantly triggers the O(n²) worst case.

Defaulting to merge sort in a memory-constrained environment (embedded systems, streaming data) without accounting for its O(n) extra array requirement.

Wikipedia — Merge sort — Data Structures & Algorithms