What it costs
- Best case
- O(n log n)Every pivot lands near the middle, so the recursion halves each time and is only log₂n deep.
- Average
- O(n log n)With a random arrangement, pivots are good enough often enough. Its constant factors are the smallest of any comparison sort, which is why it usually wins in practice despite the worst case.
- Worst case
- O(n²)Every pivot is the largest or smallest value, so each partition peels off one element and the recursion is n deep. Try the Already sorted or Reversed preset — this version takes the last element as the pivot, so sorted input is exactly the disaster case.
- Extra memory
- O(log n)Nothing is copied, but the recursion has to remember where it was. That stack is O(n) deep in the worst case, which is how a quick sort can overflow the stack on sorted input.
- Stable
- NoPartitioning swaps across long distances, so equal values get reordered. This is why libraries use quick sort for primitives and merge sort for objects, where you can tell equal elements apart.
- Fixing the worst case
- Pick betterReal implementations choose the pivot as the median of the first, middle and last, or at random, which makes the sorted-input disaster vanish. Introsort goes further and bails out to heap sort if the recursion gets too deep.
Against merge sort: quick sort needs no scratch space and is usually faster, but merge sort's O(n log n) is a guarantee where this one is only a likelihood. Run both on Already sorted to see the difference that makes.