Skip to content
Tutorials Center
My learning

Topics

Lesson 82 of 225 ยท Sorting

Quick Sort

Learn quick sort in Python. Partition schemes, pivot choices, the O(n^2) worst case, randomization, 3-way partitioning and quickselect, with traces.

Quick sort is the sorting algorithm most people meet in a computer science course and the one most real systems used to be built on. It follows the divide and conquer recipe like merge sort, but it puts the hard work in a different place. Merge sort splits the list the easy way (in half) and does the work when merging. Quick sort does the work while splitting and has nothing left to do afterwards.

The idea fits in one sentence: pick an element called the pivot, move everything smaller to its left and everything larger to its right, then sort the two sides the same way. After the split, the pivot is already in its final position, and nothing from the left side will ever need to cross to the right. In this lesson you will build quick sort twice (a readable version and an in-place version), watch its worst case happen on purpose, fix it with randomization, handle duplicates with three-way partitioning, and then reuse the same idea to find the k-th smallest element without sorting.

The idea with a picture

TEXT
sort [6, 2, 9, 4, 7, 1, 8], pivot = 6

partition:   [2, 4, 1]   6   [9, 7, 8]
              smaller  pivot  larger

recurse left:  [2, 4, 1] -> [1, 2, 4]
recurse right: [9, 7, 8] -> [7, 8, 9]

result:      [1, 2, 4]   6   [7, 8, 9]

The recursion stops when a part has zero or one element: such a list is already sorted. That is the base case. Everything else is deciding how to partition and which pivot to choose. If you want a refresher on partitioning itself, Partitioning, Dutch Flag and In-place Tricks covers Lomuto and Hoare in detail.

A readable version

The shortest correct quick sort in Python builds new lists. It is not in place, but it shows the algorithm without any index juggling.

Python Quick sort that builds new lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Putting the pivot together with its duplicates in equal means the recursion never sees the same value twice, which already protects against one common slowdown. The price is memory: every call allocates new lists, so the extra space is O(n) in total at each level of recursion. Real implementations partition in place.

In-place quick sort with Lomuto partitioning

The in-place version sorts the range a[lo..hi] by swapping elements inside the same list. We use the Lomuto scheme: take the last element as the pivot, scan from left to right, and grow a "small" region at the front.

TEXT
Lomuto invariant while scanning j:

  [ lo ... i-1 : <= pivot | i ... j-1 : > pivot | j ... hi-1 : unseen | hi : pivot ]

When the scan ends, swap the pivot into position i. Everything before i is <= pivot, everything after is > pivot, and the pivot is exactly where it will be in the final sorted list.

Here is the algorithm in plain words:

  1. If lo >= hi, the range has at most one element: stop.
  2. Partition the range and get the pivot's final index p.
  3. Sort a[lo..p-1] and a[p+1..hi].

The next example counts comparisons so you can compare variants by number of steps, not by clock time, and prints a trace for a small list.

Python In-place quick sort (Lomuto) with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace from top to bottom: each line is one partition, indented by recursion depth. After the first line, the pivot (the original last element, 7) sits at its final index, and the two sides are independent problems.

Complexity: why the pivot decides everything

Each partition of a range of size m costs m - 1 comparisons. The total cost is therefore the sum of the range sizes over all calls, and that depends on how evenly the pivot splits the range.

  • Balanced splits (best and average case). If each pivot lands near the middle, the recursion is about log n levels deep and each level does about n comparisons: O(n log n). Even a lopsided but constant-ratio split such as 90/10 stays O(n log n), because the depth is still logarithmic. The recurrence is T(n) = 2T(n/2) + n; see Recurrences and the Master Theorem.
  • Worst case. If the pivot is always the smallest or largest element, one side is empty and the other has m - 1 elements. The sizes go n, n-1, n-2, ... and the total is about nยฒ/2 comparisons: O(nยฒ). The recursion also becomes n levels deep, which in Python means a RecursionError for lists longer than about a thousand.

With "last element is the pivot", the worst case is not exotic: it is an already sorted list (or reverse sorted), the most common input in practice. Watch it happen:

Python Sorted input is the worst case for a last-element pivot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The "last" pivot on sorted input performs exactly n(n-1)/2 comparisons, the quadratic worst case. A random pivot makes every input behave like an average input. Median of three (the median of the first, middle and last elements) fixes sorted and reverse-sorted data and is cheap, but a crafted input can still defeat it.

Randomization changes what "worst case" means. With a random pivot, no input is bad in advance. The O(nยฒ) outcome is still possible, but it needs a long streak of unlucky random choices, so its probability is astronomically small. We say the expected time is O(n log n) for every input. See Randomized Algorithms.

Space: the recursion stack

In-place quick sort uses no extra lists, but the recursion uses stack space: one frame per active call. With balanced splits the depth is O(log n). With bad splits it is O(n). A standard trick keeps the stack small even in bad cases: recurse into the smaller side and loop on the larger side. The smaller side is at most half the size, so the depth can never exceed logโ‚‚ n.

Python Recursing on the smaller side only

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that 2,000 elements sorted in the worst case would have blown Python's default recursion limit with the plain version, yet the stack here never grows beyond a couple of frames. The time is still quadratic for this pivot rule, but the memory is safe.

Duplicates and three-way quick sort

Lomuto's two-way split treats elements equal to the pivot as "small". If the list has many equal values (think of sorting people by country, or a list that contains only a few distinct numbers), the split becomes lopsided and the sort slows towards O(nยฒ).

Three-way partitioning fixes this by splitting into three regions: less than, equal to and greater than the pivot. The equal region is final and is never touched again. This is the Dutch national flag partition from Partitioning.

TEXT
  [ < pivot | == pivot | unseen | > pivot ]
              lt   i          gt
Python Three-way quick sort on many duplicates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With only three distinct values among 400 numbers, the three-way version needs 812 comparisons, while the two-way version needs 27,566 because it keeps re-sorting groups of equal numbers. With all keys distinct, three-way is slightly slower because of extra bookkeeping, which is why libraries pick the scheme based on what they expect.

Quickselect: the k-th smallest without sorting

Quick sort throws away work: after partitioning, it sorts both sides. If you only need the k-th smallest element (or the median), you only need to keep the side that contains position k and ignore the other. This is quickselect. Each round costs O(size of the range) and the range shrinks, so the expected total is n + n/2 + n/4 + ... = O(n). The worst case is O(nยฒ) for the same reason as quick sort, and a random pivot makes it unlikely.

Python Quickselect for the k-th smallest

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Properties and when to use it

Property Quick sort
Best / average time O(n log n)
Worst time O(nยฒ), made very unlikely by a random pivot
Extra space O(log n) stack (in place)
Stable No: partition swaps jump over equal elements
Adaptive No (sorted input is bad for naive pivots)

Quick sort is usually the fastest comparison sort on arrays in memory, because its inner loop is a tight scan over contiguous elements (good for CPU caches) and it does few swaps. Prefer merge sort when you need stability or a guaranteed O(n log n) bound, and heap sort when you need a worst-case guarantee with O(1) extra space. Python's own sorted uses neither; see Shell Sort, Timsort and Hybrid Sorts.

Common mistakes

  • Using the first or last element on sorted data. It gives O(nยฒ) and deep recursion. Randomize or use median of three.
  • Excluding the wrong indexes after Hoare partitioning. Hoare returns a split point, not the pivot's final index; the recursion ranges are different from Lomuto's.
  • Forgetting that duplicates matter. Many equal keys need three-way partitioning.
  • Expecting stability. Sorting records by one key with quick sort scrambles earlier ordering. Use sorted (stable) when that matters; see Sorting Basics.
  • Off-by-one in the recursion ranges. The pivot is final: recurse on lo..p-1 and p+1..hi, never include p.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is true about the pivot right after a partition step?

    Everything on its left is not larger and everything on its right is not smaller, so the pivot is exactly where it belongs in the sorted result.
  2. 2. Which input makes quick sort with a last-element pivot take O(n^2) time?

    On sorted data the last element is the maximum, so every partition peels off just one element and the sizes go n, n-1, n-2, and so on.
  3. 3. How does recursing into the smaller side first (and looping on the larger) help?

    The side we recurse into has at most half the elements, so the depth can halve only about log2 n times. The running time is unchanged.
  4. 4. Why is quickselect expected to take O(n) time, not O(n log n)?

    After each partition one side is discarded, so the ranges shrink geometrically and the total work adds up to a constant times n in expectation.
  5. 5. When is three-way partitioning especially useful?

    Elements equal to the pivot are grouped in the middle and never processed again, so lists with few distinct values are sorted quickly.

Summary

  • Quick sort picks a pivot, partitions the range so smaller values are on the left and larger on the right, then sorts both sides recursively.
  • The pivot is in its final position after partitioning; the base case is a range of at most one element.
  • Time is O(n log n) on average and for balanced splits, and O(nยฒ) in the worst case, for example a sorted list with a last-element pivot.
  • A random pivot or median of three avoids the common bad inputs; a random pivot makes the expected time O(n log n) for every input.
  • In-place quick sort needs O(log n) stack if you recurse on the smaller side; it is not stable.
  • Three-way partitioning handles many duplicates, and quickselect reuses partitioning to find the k-th smallest in expected O(n).

Next: Heap Sort, a sort with a guaranteed O(n log n) worst case and no extra memory.