How Quicksort Works

Recursive functions that forget their base case run until the call stack overflows. Quicksort's base case is the cheapest one available: any list with fewer than two items is already sorted by definition, so the function returns it untouched. The check on lines 31 and 32 happens before any work, before the random pivot is even chosen, and it is what stops every recursive branch in the tree. The signature itself is plain: a list in, a list out, no Comparable bound and no generics. That keeps the doctests readable and the implementation focused on the algorithm rather than the type system. Each recursive call eventually hits a list of length zero or one and unwinds.

Quicksort's average performance depends on the pivot landing somewhere near the median. A naive choice (always the first element) collapses to O(n squared) on already-sorted input because every partition produces one empty side and one full side. randrange(len(collection)) on line 35 picks a random index instead, which gives an expected balanced split across all input distributions. After the random pick, the pivot is removed from the list with pop so it does not appear in either half. Two list comprehensions on lines 39 and 40 then walk the remaining elements once each and sort them into lesser and greater by comparing against the pivot. Partitioning therefore costs O(n) per recursion level.

The recursive return is the line that turns partitioning into sorting. quick_sort(lesser) recursively sorts every element less than or equal to the pivot, quick_sort(greater) does the same for the strictly greater elements, and the list-spread syntax on line 43 unpacks both sorted halves into a new list with the pivot dropped between them. Because every element in lesser is at most the pivot and every element in greater is strictly above it, that concatenation is itself sorted. The recursion tree has depth O(log n) on average, and each level does O(n) partition work, which is where the O(n log n) average complexity comes from. The pivot only appears once in the output because it was popped from the input before the recursion fired.

The function docstring is also the test suite. CI runs pytest --doctest-modules, which parses every >>> line in the file, executes the expression, and asserts the next line matches the actual output. Three examples appear here. quick_sort([0, 5, 3, 2, 2]) proves the sort handles duplicates and produces ascending order. quick_sort([]) proves the base case returns the empty list rather than raising. quick_sort([-2, 5, 0, -45]) proves negative numbers and zero work the same as positive ones. A reviewer reading these six lines knows the function's contract. A future change that breaks any of these examples fails the build before the PR can merge.

A self-contained algorithm file needs a way to be exercised by hand, and the __main__ guard is the convention every algorithm file in the repository follows. Importing this module from another file does not run the block, because the __name__ check is only true when Python is invoked directly with the file as its argument. The driver itself reads a comma-separated string from stdin, splits it, converts each token with int(), and prints the sorted list. The contribution guide bans bare input() calls without strip() because trailing whitespace would break the integer parse, which is why .strip() appears on line 48. Compare with sorts/insertion_sort.py for the same pattern with an additional doctest.testmod() call.