Quick Sort: Overview, Naïve Implementation, Optimizations, and Non‑Recursive Version

0 Overview

Quick sort is a divide‑and‑conquer algorithm similar to merge sort but without a merge step. It partitions an array A[p..r] into two subarrays A[p..q‑1] and A[q+1..r] so that every element in the left part is ≤ A[q] and every element in the right part is > A[q]. The three steps are partition, recursive sorting of the subarrays, and no merging.

The algorithm is simple but easy to implement incorrectly, which can lead to infinite loops or incorrect partitions.

Source code repository: https://github.com/shishujuan/dsalg/tree/master/code/alg/sort

1 Naïve Quick Sort

The naïve version suffers from O(N²) time complexity when the input is already sorted or when all elements are equal. The following C code shows the basic implementation.

/**
 * 快速排序-朴素版本
 */
void quickSort(int a[], int l, int u) {
    if (l >= u) return;
    int q = partition(a, l, u);
    quickSort(a, l, q-1);
    quickSort(a, q+1, u);
}
/**
 * 快速排序-划分函数
 */
int partition(int a[], int l, int u) {
    int i, q = l;
    for (i = l+1; i <= u; i++) {
        if (a[i] < a[l])
            swapInt(a, i, ++q);
    }
    swapInt(a, l, q);
    return q;
}

2 Improved Two‑Way Partition Quick Sort

This improvement uses two indices i and j that scan from opposite ends, swapping elements that are on the wrong side of the pivot. It handles arrays with many equal elements better, reducing the worst‑case from O(N²) to roughly O(N log N).

Example: for an array of identical elements the naïve method repeatedly creates partitions of size 1 and N‑1, while the two‑way method can split the array near the middle.

/**
 * 快速排序-双向划分函数
 */
int partitionLR(int a[], int l, int u, int pivot) {
    int i = l;
    int j = u+1;
    while (1) {
        do { i++; } while (a[i] < pivot && i <= u); // avoid out‑of‑bounds
        do { j--; } while (a[j] > pivot);
        if (i > j) break;
        swapInt(a, i, j);
    }
    // swap pivot (at l) with element at j
    swapInt(a, l, j);
    return j;
}
/**
 * 快速排序-双向划分法
 */
void quickSortLR(int a[], int l, int u) {
    if (l >= u) return;
    int pivot = a[l];
    int q = partitionLR(a, l, u, pivot);
    quickSortLR(a, l, q-1);
    quickSortLR(a, q+1, u);
}

Even with two‑way partitioning, a completely sorted array still degrades to O(N²), and care must be taken to avoid infinite loops when elements equal the pivot.

3 Further Improvements – Random and Median‑of‑Three Pivot Selection

Choosing the pivot randomly or using the median of three (first, middle, last) elements improves balance and reduces the chance of worst‑case partitions.

/**
 * 随机选择枢纽元
 */
int pivotRandom(int a[], int l, int u) {
    int rand = randInt(l, u);
    swapInt(a, l, rand); // move pivot to position l
    return a[l];
}
/**
 * 三数取中选择枢纽元
 */
int pivotMedian3(int a[], int l, int u) {
    int m = l + (u - l) / 2;
    if (a[l] > a[m]) swapInt(a, l, m);
    if (a[l] > a[u]) swapInt(a, l, u);
    if (a[m] > a[u]) swapInt(a, m, u);
    // now a[l] <= a[m] <= a[u]
    swapInt(a, m, l); // move median to l
    return a[l];
}

When the data is nearly sorted, switching to insertion sort for small sub‑arrays yields better performance.

4 Non‑Recursive Quick Sort

A stack‑based iterative version avoids recursion. It pushes the bounds of sub‑arrays onto a stack and processes them until the stack is empty.

/**
 * 快速排序-非递归版本
 */
void quickSortIter(int a[], int n) {
    Stack *stack = stackNew(n);
    int l = 0, u = n-1;
    int p = partition(a, l, u);
    if (p-1 > l) { push(stack, p-1); push(stack, l); }
    if (p+1 < u) { push(stack, u); push(stack, p+1); }
    while (!IS_EMPTY(stack)) {
        l = pop(stack);
        u = pop(stack);
        p = partition(a, l, u);
        if (p-1 > l) { push(stack, p-1); push(stack, l); }
        if (p+1 < u) { push(stack, u); push(stack, p+1); }
    }
}

References: "Data Structures and Algorithms – C Implementation" and "Introduction to Algorithms".