Quick Sort in Python
Pick a pivot, split the list into smaller, equal and larger parts, and sort each part the same way.
- Choosing a pivot
- Partitioning with list comprehensions
- Average O(n log n) versus worst-case O(n²)
[7, 8, 1, 5]
- sort again
[9]
- already in place
[10]
- one value: done
Partition around a pivot
The problem
Quicksort is one of the most widely used sorting ideas because it is fast on average and easy to express. It shows another way to divide a problem: instead of splitting in the middle, split around a chosen value.
Think of it like this
Quicksort is like sorting books by height around one chosen book. Put every shorter book on the left pile, every taller book on the right pile and books of the same height in the middle. Then sort each side pile the same way, and put the piles back together.
pivot = values[len(values) // 2]📕 Choose one book to compare againstlower = [... if value < pivot]⬅️ Shorter books to the lefthigher = [... if value > pivot]➡️ Taller books to the rightquick_sort(lower) + equal + quick_sort(higher)📚 Sort each side, then join the pilesQuicksort picks a pivot, splits the other items into those smaller and larger than it, sorts each part recursively and joins them, taking O(n log n) time on average.
Key points
if len(values) <= 1:is the base case: such a list is already sorted.pivot = values[len(values) // 2]takes the middle value as the pivot.lower,equalandhighersplit the values around the pivot;equalkeeps duplicates together.quick_sort(lower) + equal + quick_sort(higher)sorts the two sides and joins the three lists.
When should you use it?
- Learning partitioning and recursion.
- General-purpose in-place sorting in languages and libraries (with careful pivot choice).
- Selection problems such as finding the median (quickselect uses the same partition).
When not to use it
- Normal Python code:
sorted()is faster and stable. - When a guaranteed worst case matters: bad pivots make quicksort
O(n²); merge sort never is.
Quick Sort in Python visualizer
O(n log n)Use Play or Step to follow each comparison and data movement.
Example code
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Result of running the code
[1, 5, 7, 8, 9, 10]
Code explanation
This readable version creates three partitions. Average time complexity is O(n log n), although poor pivot choices can produce O(n²).
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Dropping values equal to the pivot
With only < and >, duplicates of the pivot disappear.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
All challenges