Quick sort in Python

Quick sort picks one item, the pivot. It puts the items smaller than the pivot in one list and the larger items in another, sorts those two lists with the same function (recursion), and joins the results around the pivot.

The program

def quick_sort(items):
    if len(items) <= 1:
        return list(items)             # a new list, even for 0 or 1 items
    pivot = items[len(items) // 2]
    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 quick_sort(smaller) + equal + quick_sort(larger)

numbers = [33, 10, 55, 71, 29, 3, 18, 42]
print(quick_sort(numbers))
print(numbers)
print(quick_sort([]))
print(quick_sort([4, 1, 4, 4, 2]))

[3, 10, 18, 29, 33, 42, 55, 71]
[33, 10, 55, 71, 29, 3, 18, 42]
[]
[1, 2, 4, 4, 4]

How it works

• The base case is a list of 0 or 1 items, which is already sorted. Each recursive call gets a shorter list, because the pivot itself is never in smaller or larger.
• The three list comprehensions build new lists, so the caller's list is not changed, as the second line of output shows.
• The equal list keeps every copy of the pivot. Without it, a list with many equal values would lose the duplicates or never finish.
• The pivot here is the middle item. If you always took the first item, an already sorted list would split into an empty part and everything else, at every step.

Watching the calls

The same function with a depth argument, printing each call with more indentation the deeper it goes:

def quick_sort(items, depth=0):
    indent = "  " * depth
    if len(items) <= 1:
        print(f"{indent}{items}")
        return list(items)
    pivot = items[len(items) // 2]
    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]
    print(f"{indent}{items} pivot {pivot}: {smaller} {equal} {larger}")
    return quick_sort(smaller, depth + 1) + equal + quick_sort(larger, depth + 1)

print(quick_sort([33, 10, 55, 71, 29, 3, 18, 42]))

[33, 10, 55, 71, 29, 3, 18, 42] pivot 29: [10, 3, 18] [29] [33, 55, 71, 42]
  [10, 3, 18] pivot 3: [] [3] [10, 18]
    []
    [10, 18] pivot 18: [10] [18] []
      [10]
      []
  [33, 55, 71, 42] pivot 71: [33, 55, 42] [71] []
    [33, 55, 42] pivot 55: [33, 42] [55] []
      [33, 42] pivot 42: [33] [42] []
        [33]
        []
      []
    []
[3, 10, 18, 29, 33, 42, 55, 71]

In the second branch the pivot is 71, the largest item, so larger is empty and the list gets only one item shorter. That is a bad pivot. On average, quick sort does about n × log2(n) comparisons, like merge sort. When the pivot is a bad choice again and again (always the smallest or largest item), the parts shrink by only one item each time, and it becomes as slow as bubble sort: about n²/2 comparisons. This version also makes new lists at every step. The classic version swaps items inside one list instead, to save memory. In real code, use sorted(items).