Quick sort chooses a pivot and partitions the input into values smaller and larger than that pivot. It then sorts the partitions recursively.
It is important because it shows how partitioning strategy affects average and worst-case behavior.
Core Idea
The partition step puts values on the correct side of the pivot. After partitioning, the pivot is in a meaningful position, and the left and right parts can be handled separately.
Quick sort is often O(n log n) on average, but poor pivot choices can lead to O(n^2) time.
Unlike merge sort, quick sort organizes the data around values, not around equal-sized position splits. A good pivot creates balanced partitions. A bad pivot creates one large partition and one tiny partition.
Function Contract
quick_sort(values) expects a list of comparable values.
It returns a new sorted list and does not modify the original list. The example groups values into smaller, equal, and larger, so duplicates are handled explicitly.
Python Example
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
smaller = [x for x in values if x < pivot]
equal = [x for x in values if x == pivot]
larger = [x for x in values if x > pivot]
return quick_sort(smaller) + equal + quick_sort(larger)This version is readable but not in-place.
Step-by-Step Example
For [5, 2, 8, 1, 3], choose 8 as the middle pivot in this simple version:
smaller = [5, 2, 1, 3]
equal = [8]
larger = []The right side is empty, so this pivot choice is not balanced. The recursive call must still sort [5, 2, 1, 3].
If a pivot splits the input more evenly, recursion becomes shallower.
Why It Works
After partitioning, every value in smaller is less than the pivot, every value in equal equals the pivot, and every value in larger is greater than the pivot.
If the recursive calls correctly sort smaller and larger, then:
sorted(smaller) + equal + sorted(larger)is sorted because every left value belongs before every pivot value, and every right value belongs after it.
Complexity
When partitions are balanced, each level does O(n) partition work and there are O(log n) levels, giving O(n log n) average behavior. When partitions are extremely unbalanced, there can be O(n) levels, giving O(n^2) time.
The readable Python version uses extra lists. In-place quick sort has different implementation details and still uses recursion stack space.
Common Confusions
The simple Python version above is useful for learning, not for replacing Python’s built-in sort.
Quick sort’s performance depends on partition balance. If one side is almost always empty, recursion becomes deep and slow.
Another common mistake is forgetting to handle values equal to the pivot. Without the equal group or a careful in-place partition, duplicates can cause awkward behavior.
When To Use It
Use quick sort as a study topic for partitioning, recursion, average-case reasoning, and the difference between elegant pseudocode and production sorting tools.
Do not implement quick sort for ordinary Python sorting needs. Use sorted or .sort() unless the exercise is specifically about the algorithm.
The Main Point
Quick sort is about partitioning around a pivot. Its average behavior is good when partitions are balanced, but bad pivots can make the recursion deep.