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.
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.
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.
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.