Quicksort

The short version

Quicksort picks a pivot, puts smaller items on one side and larger items on the other, then sorts each side the same way.

Details

With a good pivot the sides are about equal and the work is n log n. With a bad pivot, such as always taking the first item of a sorted list, one side is empty every time and the work becomes n squared. Picking a random pivot makes that unlikely.

Try it yourself

import random

def quicksort(items):
    if len(items) <= 1:
        return items
    pivot = random.choice(items)
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)

print(quicksort([5, 2, 9, 1, 5]))

You should see [1, 2, 5, 5, 9].

Explain it to the duck

What input makes quicksort slow when the pivot is always the first item, and why?

Tested with: Python 3.13.