# Quick Sort visualised: Lomuto partition with pivot

> Interactive Quick Sort: pick a pivot, partition smaller and larger values, recurse on both halves. Average O(n log n), worst case O(n^2), in-place, not stable.

Address: https://marckimmel.de/en/informatik/sortieralgorithmen/quick-sort
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen/quick-sort.md

Picks a pivot, partitions into smaller and larger, then sorts both sides recursively.

Quick Sort picks a pivot element (the Lomuto variant used here uses the last element of the range) and partitions the array so that every value left of the pivot is less or equal to the pivot and every value to the right is larger. A pointer i tracks the boundary of the "small" region; a second pointer j walks across all elements, and whenever a[j] <= pivot, a[j] is swapped forward into the small region. At the end the pivot is moved between the two parts. The pivot is now in its final position; the two parts are sorted recursively. With a good pivot choice the range halves every step, producing O(n log n) average and best-case runtime. In the worst case (e.g. an already-sorted input with a bad pivot) the recursion degenerates into a list and the runtime falls to O(n^2). Quick Sort works in-place but needs O(log n) stack memory for the recursion. The algorithm is not stable because swaps over a distance can move equal values past each other.

Default sorter in most standard libraries, often as an Introsort variant that falls back to Heap Sort. In practice faster than Merge Sort thanks to in-place operation and cache-friendly memory access. Choose it when memory is tight and stability is not required.

## Frequently asked questions

### What is the difference between the Lomuto and the Hoare partition?

Lomuto takes the last element as pivot and moves all smaller values to the front with a single pointer, after which the pivot sits at its final position. Hoare runs two pointers towards each other from both ends and swaps pairs that are on the wrong side. Hoare needs about a third of the swaps on average, Lomuto is easier to follow and is the one shown here.

### Why is Quick Sort quadratic in the worst case?

If the pivot is always the smallest or largest value, for example on already sorted input with the last element as pivot, the partition splits the array into an empty part and a part one shorter. The recursion then goes n levels deep, and the comparisons add up to O(n^2). A random pivot or the median of three values makes this case very unlikely.

### Is Quick Sort stable?

No. The partition swaps elements across long distances, and equal values can lose their original order. If you need stability, use Merge Sort or Timsort.

## Related

- [Sorting Algorithms](https://marckimmel.de/en/informatik/sortieralgorithmen.md)