Quick Sort

Quicksort partitions values around a pivot, then sorts the regions below and above it. Good splits give O(n log n) work, while repeatedly unbalanced splits can give O(n²). We use three-way partitioning so duplicate pivot values are finished together, pseudorandom pivot selection for practical balance, and smaller-side recursion to bound stack depth. Randomization improves expected behavior but is not a worst-case time guarantee.

Prerequisites: Recursion; Sorting; loop invariants.

Build the idea

1. 1. State the partition regions

   For inclusive [l,r], maintain values before lt below pivot, positions lt..i−1 equal, positions i..gt unclassified, and positions after gt above pivot. Choose pivot as a copied value, not a reference to an element that swaps may move. This invariant describes exactly what every pointer means.

2. 2. Classify one unknown value

   If a[i]<pivot, swap it with a[lt] and advance both. If a[i]>pivot, swap it with a[gt] and decrement gt but DO NOT advance i: the incoming value has not been classified. On equality advance i only. Every iteration shrinks the unknown region, so partitioning terminates after O(length) classifications.

3. 3. Finish equal values and recurse

   When i>gt, [lt,gt] contains only pivot-equal values and is already finished. Sort [l,lt−1] and [gt+1,r]. All-equal input needs only one linear partition rather than deep repeated equal-key splits. The code recursively processes the smaller unequal region and continues the larger one with a loop; each recursive child is at most half the parent’s size, giving O(log n) stack even if time becomes quadratic.

4. 4. Visualize a split

   For values [3,1,3,2,5] and an illustrative pivot 3, the partition forms some ordering of [1,2], then [3,3], then [5]. The exact order within the less/greater regions may differ; they are recursively sorted. The final sequence is [1,2,3,3,5]. Quicksort is not stable: swaps can change relative order among records with equal keys.

5. 5. Qualify the average-case statement

   Uniform independently random pivots yield expected O(n log n) time for a fixed input. This program uses a fixed-seed pseudorandom generator for reproducible demonstrations; adversarial inputs or pivot sequences still allow O(n²). First/last deterministic pivots often suffer on sorted data. std::sort adds worst-case protections and is usually preferable for general contest sorting; this lesson teaches partitioning mechanics, not a replacement for library safeguards.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<random>
void quickSort(std::vector<int>&a,int l,int r,std::mt19937&random){
    while(l<r){
        int pivot=a[std::uniform_int_distribution<int>(l,r)(random)];
        int lt=l,i=l,gt=r;
        while(i<=gt){
            if(a[i]<pivot){
                std::swap(a[lt++],a[i++]);
            }
            else if(a[i]>pivot){
                std::swap(a[i],a[gt--]); // Inspect swapped-in item next.
            }
            else{
                ++i;
            }
        }
        // Equal interval [lt,gt] is finished. Recurse only on the smaller side.
        if(lt-l<r-gt){
            quickSort(a,l,lt-1,random);
            l=gt+1;
        }
        else{
            quickSort(a,gt+1,r,random);
            r=lt-1;
        }
    }
}
int main(){
    int n;
    std::cin>>n;
    std::vector<int>a(n);
    for(int&x:a){
        std::cin>>x;
    }
    std::mt19937 random(712367); // Reproducible pseudorandom pivots for the lesson.
    quickSort(a,0,n-1,random);
    for(int i=0;i<n;++i){
        std::cout<<a[i]<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

Expected O(n log n) time under the random-pivot model; O(n²) worst-case time remains. Three-way partitioning gives O(n) on all-equal input. The smaller-side-recursion/loop implementation uses O(log(n+1)) stack in the worst case and O(1) other auxiliary array storage. Input vector is O(n); no output stability is guaranteed.

Example input and output

Read n (0..200000), then n int values. Print ascending values, or a blank line for empty input.

Input

5
3 1 3 2 5

Output

1 2 3 3 5

A partition around 3 groups smaller values, the two 3s and larger values; recursive subranges finish the order.

Practical applications

Use quicksort to understand partitioning, quickselect and efficient in-memory sorting. For a strong worst-case sorting guarantee use merge sort or std::sort. Three-way partitioning is particularly helpful with many duplicates. Stable output requires another method or explicit tie keys.

Check your understanding

Why is i unchanged after swapping with a[gt]?

Put it into practice

Test sorted, reverse-sorted, all-equal and two-value arrays.