Step 3 of 6

Quicksort and partitioning

Quicksort picks a pivot, partitions the array so smaller elements come before it and larger after, then recursively sorts both sides. No merging needed.

• O(n log n) on average, in place, and very fast in practice.
• O(n²) worst case with bad pivots (for example, always the last element of already-sorted data). That's why real implementations pick pivots carefully and std::sort falls back to heapsort when recursion gets too deep ("introsort").

The Lomuto partition, using the last element as the pivot:

pivot = v[hi]; i = lo
for j in lo..hi-1:
    if v[j] < pivot: swap(v[i], v[j]); i++
swap(v[i], v[hi])     // pivot lands at its final position i
return i

Your turn: write int partition(std::vector<int>& v, int lo, int hi) (inclusive range) and void quick_sort(std::vector<int>& v, int lo, int hi).

Previous: Merge sort Next: Counting sort