
Quicksort sorts by partitioning values around a pivot, then recursively sorting each side. See how pivot placement differs from schemes such as Lomuto and Hoare.
What is quick sort?
Quick sort, also called quicksort, sorts a collection by choosing a pivot, partitioning the values around it, and then sorting the resulting parts in the same way.
The pivot is a value taken from the part being sorted. After partitioning, values on one side belong before the pivot and values on the other side belong after it. The two sides can then be sorted independently.
Why does the pivot need partitioning?
Suppose we want to sort [6, 2, 8, 3, 1] and choose 6 as the pivot. Three values are smaller than 6: 2, 3 and 1. With positions counted from zero, 6 belongs at index 3 in the finished array.
But knowing the pivot’s position is not enough. If we simply swap 6 into index 3, we might get [3, 2, 8, 6, 1]. The value 8 is still on the left of 6, and 1 is on its right. The array has the right number of values on each side, but it is not partitioned.
A valid partition could be [2, 3, 1, 6, 8]. Every value left of 6 is smaller, and every value right of it is greater. The order within each side does not matter yet; recursion will sort those parts.
How does a partition place the pivot?
There are several partitioning schemes. Here is one called Lomuto partitioning. It uses the last value as the pivot and a boundary called i: everything before i has already been found to be smaller than the pivot.
Consider the subarray [5, 3, 1, 8, 7], with 7 as the pivot. The scan sees 5, 3 and 1. Each is smaller, so the boundary moves past it. The value 8 leaves the boundary at index 3. When the scan ends, the algorithm swaps the pivot 7 with 8 at index 3. The result is [5, 3, 1, 7, 8].
That final swap is caused by the boundary, not by a special comparison between 8 and 7 after the scan. The boundary has collected all smaller values on the left and points to the first place where the pivot can go. The swap puts the pivot there; the larger value it replaces moves to the right side.
With the strict comparison used here, values equal to the pivot go on its right. Other schemes can use different rules, so their boundaries and returned positions may mean something different.
Work through a dry run
Use the arrows beside the example name to change the array. The step buttons move through one dry run. Watch j scan the array while i marks the next place for a value smaller than the pivot.
In the scratch pad, compare the current value with the pivot, decide whether to swap, and move the indices yourself. Each action adds a row. Reveal the reference run when you are ready to compare. Loading interactive comparison…
What does quick sort do?
The conceptual algorithm has three steps:
- Choose a pivot in the current part of the array.
- Partition the values around the pivot, placing it or a dividing boundary where the chosen scheme requires.
- Recursively quick-sort the parts on either side.
The process stops when a part has zero or one value, because it is already sorted.
In Lomuto’s scheme, the pivot finishes at its final position in each partition step. A recursive call can skip that position:
quick_sort(values, low, high)
if low >= high
return
pivot_index = lomuto_partition(values, low, high)
quick_sort(values, low, pivot_index - 1)
quick_sort(values, pivot_index + 1, high)The partition function does the scan and final swap described above. Quicksort itself does not require this exact procedure.
Is Lomuto the quick sort algorithm?
Lomuto and Hoare are names for partitioning schemes, not separate names for the overall idea. They organise comparisons and swaps differently. In Lomuto partitioning, the pivot is put into its final position at the end of each pass. A common form of Hoare partitioning returns a dividing boundary; the pivot itself may not be in its final sorted position after that pass.
So it helps to keep three levels separate:
- Quicksort: partition, then recursively sort the parts.
- Partitioning scheme: the method that rearranges values and defines the resulting boundaries.
- Implementation choices: how to choose a pivot, handle equal values, reduce recursion, or switch to another method for small parts.
How fast is quick sort?
When partitions are reasonably balanced, quicksort takes about O(n log n) time. Each level of partitioning scans the values in the current parts, and balanced splits produce about log n levels.
If each pivot repeatedly leaves one very large part and one tiny part, the work can grow to O(n²). Choosing a random pivot or using a median-of-three choice makes consistently poor splits less likely, though it does not change the worst-case bound for ordinary quicksort.
Many partitioning schemes rearrange the array in place, using little extra working storage. The recursive calls still use a stack: about O(log n) space for balanced splits and up to O(n) for very uneven splits.
What is the central idea?
Counting how many values are smaller than a pivot can tell us where it belongs, but the count alone does not put the other values on the correct sides. Partitioning does that work. Once the pivot or dividing boundary separates the problem into smaller parts, the same reasoning can be applied again.
Quicksort is therefore both a simple idea and a family of implementations. The pivot rule and partitioning scheme determine how that idea behaves on real data.
References
Ai disclosure: written with the help of AI (ChatGPT). You are encouraged to point out errors and omissions.






