Merge Sort and Quick Sort

Merge Sort and Quick Sort are the two premier divide-and-conquer sorting algorithms in computer science.

1. Merge Sort

Merge Sort divides an array into two halves of equal size $\lfloor n/2 \rfloor$ , recursively sorts each half, and merges the two sorted sub-arrays into a single sorted array.

Diagram loads as you scroll.

Algorithm Pseudocode

MergeSort(A[0..n-1]):
    if n > 1 then:
        copy A[0..floor(n/2)-1] to B[0..floor(n/2)-1]
        copy A[floor(n/2)..n-1] to C[0..ceil(n/2)-1]
        MergeSort(B)
        MergeSort(C)
        Merge(B, C, A)

Merge(B[0..p-1], C[0..q-1], A[0..p+q-1]):
    i = 0; j = 0; k = 0
    while i < p and j < q do:
        if B[i] <= C[j] then:
            A[k] = B[i]; i = i + 1
        else:
            A[k] = C[j]; j = j + 1
        k = k + 1
    if i == p then copy C[j..q-1] to A[k..p+q-1]
    else copy B[i..p-1] to A[k..p+q-1]

Efficiency Analysis

Number of key comparisons in merging two lists of size $n/2$ $n /2$ :
- Worst case: $n - 1$ comparisons.
- Best case: $n/2$ comparisons.
Recurrence relation:

C(n) = 2 C(n / 2) + C_{\text{merge}}(n) \quad \text{for } n > 1, \quad C(1) = 0

C_{\text{worst}}(n) = 2 C(n / 2) + n - 1 \implies \Theta(n \log_2 n)

All Cases: Best, worst, and average are all $\Theta(n \log n)$ .
Auxiliary Space: $\Theta(n)$ for auxiliary buffers during merge.
Stability: Stable (the condition B[i] <= C[j] preserves relative order of duplicate keys).

2. Quick Sort

Quick Sort partitions an array according to a selected pivot element $p$ , placing all elements $< p$ to its left and all elements $> p$ to its right. It then recursively sorts the sub-arrays to the left and right of the pivot.

Diagram loads as you scroll.

Hoare Partition Algorithm

HoarePartition(A[l..r]):
    p = A[l]   // pivot is first element
    i = l
    j = r + 1
    repeat:
        repeat i = i + 1 until A[i] >= p or i >= r
        repeat j = j - 1 until A[j] <= p
        swap(A[i], A[j])
    until i >= j
    swap(A[i], A[j])   // undo last swap when pointers crossed
    swap(A[l], A[j])   // place pivot in final split position
    return j

Efficiency Analysis

Worst-Case: Occurs when the pivot is always the extreme element (e.g., sorting an already sorted or reverse-sorted array with first-element pivot).
- Subproblem sizes: $0$ and $n - 1$ .
$C_{\text{worst}}(n) = C(n - 1) + (n + 1) \implies \Theta(n^2)$
Best-Case: Occurs when the pivot always divides the array into two equal halves of size $\lfloor n/2 \rfloor$ : $C_{\text{best}}(n) = 2 C(n / 2) + \Theta(n) \implies \Theta(n \log n)$
Average-Case: Averaged across all input permutations: $C_{\text{avg}}(n) \approx 2n \ln n \approx 1.386 n \log_2 n \in \Theta(n \log n)$ Quick Sort’s inner loop has a lower constant factor than Merge Sort, making it faster in practice for in-memory sorting.
Auxiliary Space:
- In-place partitioning: no extra data array needed.
- Call stack: Best/Average case $\Theta(\log n)$ , Worst case $\Theta(n)$ .
Stability: Not stable due to long-distance swaps.

Comparison Summary

Attribute	Merge Sort	Quick Sort
Worst-Case Time	$\Theta(n \log n)$	$\Theta(n^2)$
Average-Case Time	$\Theta(n \log n)$	$\Theta(n \log n)$ (smaller constant)
Best-Case Time	$\Theta(n \log n)$	$\Theta(n \log n)$
Auxiliary Memory	$\Theta(n)$ extra buffer	$\Theta(\log n)$ call stack (in-place)
Stability	Stable	Not stable
Divide Strategy	Position-based (split exactly in half)	Value-based (split around pivot)

Exercises

Exercise 1

Trace Hoare’s partition on the array A = [5, 3, 1, 9, 8, 2, 4, 7] with A[0] = 5 as the pivot. Show pointer movements and final array.

Show solution ↓

Solution

Pivot $p = 5$ . $l = 0, r = 7$ .

Scan $i$ right until $A[i] \ge 5$ : $A[3] = 9 \ge 5 \implies i = 3$ .
Scan $j$ left until $A[j] \le 5$ : $A[6] = 4 \le 5 \implies j = 6$ .
$i < j$ , swap $A[3]$ and $A[6]$ : [5, 3, 1, 4, 8, 2, 9, 7].
Resume $i$ : stops at $A[4] = 8 \ge 5 \implies i = 4$ .
Resume $j$ : stops at $A[5] = 2 \le 5 \implies j = 5$ .
$i < j$ , swap $A[4]$ and $A[5]$ : [5, 3, 1, 4, 2, 8, 9, 7].
Resume $i$ : stops at $A[5] = 8 \ge 5 \implies i = 5$ .
Resume $j$ : stops at $A[4] = 2 \le 5 \implies j = 4$ .
Now $i \ge j$ (pointers crossed: $i=5, j=4$ ).
Swap pivot $A[0] = 5$ with $A[j] = A[4] = 2$ : [2, 3, 1, 4, 5, 8, 9, 7]

Split position: index $j = 4$ (value 5). Left partition: [2, 3, 1, 4] (all $< 5$ ). Right partition: [8, 9, 7] (all $> 5$ ).

Exercise 2

How does the “median-of-three” pivot selection strategy prevent Quick Sort from hitting its $\Theta(n^2)$ worst-case behavior on sorted inputs?

Show solution ↓

Solution

The median-of-three strategy chooses the median of the first, middle, and last elements ( $A[l], A[\lfloor (l+r)/2 \rfloor], A[r]$ ) as the pivot.

On sorted or reverse-sorted inputs, the first element is extreme (minimum or maximum), which normally causes degenerate $\Theta(n^2)$ behavior.
With median-of-three, the true median of the endpoints and middle element is chosen, guaranteeing a non-empty split on both sides and restoring $\Theta(n \log n)$ performance on sorted arrays.