Quick Sort One-Liner in Python
The functional Quicksort one-liner in Python is a classic teaching artifact: it is short enough to fit on one line and shows comprehensions plus recursion working together. This snippet covers the three-way functional one-liner, an in-place Lomuto-partition variant for performance, and a benchmark contrast against `sorted` to show why the one-liner is for teaching, not production.
659 views
7
def quicksort(xs):
if len(xs) <= 1:
return xs
pivot = xs[0]
less = [x for x in xs[1:] if x <= pivot]
more = [x for x in xs[1:] if x > pivot]
return quicksort(less) + [pivot] + quicksort(more)
print(quicksort([3, 6, 1, 5, 4, 2])) # [1, 2, 3, 4, 5, 6]
print(quicksort([1])) # [1]
print(quicksort([])) # []The functional Quicksort partitions the list into 'less than or equal to pivot' and 'greater than pivot' using two list comprehensions, then recursively sorts each side and concatenates. The base case (len(xs) <= 1) covers both the empty list and the single-element list. This is the teaching version: it is concise enough to fit on a slide and demonstrates Quicksort's divide-and-conquer shape clearly. The trade-off is O(n) extra space per recursive call (the two new lists), which makes it asymptotically slower than the in-place version for large inputs.
def quicksort_inplace(xs, lo=0, hi=None):
if hi is None:
hi = len(xs) - 1
if lo >= hi:
return
pivot = xs[hi]
i = lo
for j in range(lo, hi):
if xs[j] <= pivot:
xs[i], xs[j] = xs[j], xs[i]
i += 1
xs[i], xs[hi] = xs[hi], xs[i]
quicksort_inplace(xs, lo, i - 1)
quicksort_inplace(xs, i + 1, hi)
arr = [3, 6, 1, 5, 4, 2]
quicksort_inplace(arr)
print(arr) # [1, 2, 3, 4, 5, 6]The Lomuto partition picks the last element as the pivot, walks the unsorted region with j, and maintains an i index for the boundary between the 'less than or equal' prefix and the 'greater than' suffix. After the loop, swapping xs[i] with the pivot puts it in its final position. The recursion sorts the two sides in place. This version uses O(1) extra space and is closer to what production sort routines look like (though they pick the pivot more carefully). Worst case is still O(n^2) for adversarial inputs; introsort fixes that.
import random
large = [random.randint(0, 10000) for _ in range(50)]
# All three produce the same sorted output
functional = quicksort(list(large))
in_place = list(large)
quicksort_inplace(in_place)
builtin = sorted(large)
print(functional == builtin) # True
print(in_place == builtin) # True
print(builtin[:5]) # First 5 sorted elementsBoth Quicksort versions are educational: in production code, sorted() (and list.sort()) use Timsort, which is a stable, adaptive merge sort that runs in O(n log n) worst case and O(n) on already-sorted inputs. Timsort is implemented in C and beats hand-rolled Python by orders of magnitude. The lesson: write the one-liner to teach Quicksort, but reach for sorted for any real workload. The same advice applies in JavaScript (Array.sort is Timsort in V8) and most modern languages.