# Quick Sort — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/quick-sort

> Partition around a pivot, recurse on each side — fast in place, O(n log n) average.

## Partition around a pivot

Pick a pivot. Rearrange so everything smaller is left of it and everything larger is right — now the pivot is in its final spot. Recurse on the two sides. Average `O(n log n)`; worst `O(n^2)` if the pivot is always the min/max.

## Lomuto partition

`i` tracks the boundary of the "smaller than pivot" zone.

```python
def quick_sort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return a
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]   # pivot to its place
    quick_sort(a, lo, i - 1)
    quick_sort(a, i + 1, hi)
    return a
```

## Why it's the default

In place (`O(log n)` stack), cache-friendly, and small constants make it faster than merge sort in practice. Randomising or median-of-three pivot selection makes the `O(n^2)` case vanishingly rare. Not stable.

## Related trick

Quickselect reuses partition to find the k-th smallest element in `O(n)` average without fully sorting.