Quicksort in Python

A divide-and-conquer sort that is short to write and fast in practice.

def quicksort(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    left = [x for x in items if x < pivot]
    mid = [x for x in items if x == pivot]
    right = [x for x in items if x > pivot]
    return quicksort(left) + mid + quicksort(right)

How it works

1. Picks the middle element as a pivot.
2. List comprehensions split values below, equal to, and above the pivot.
3. Recursively sorts both sides and stitches the three parts together.

Keywords and builtins used here

• def
• for
• if
• len
• quicksort
• return

The run, in numbers

Lines

8

Characters to type

251

Tokens

80

Three-star pace

100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 48 seconds.

Type this snippet

Step 3 of 5 in Algorithms, step 53 of 72 in Language basics.

← Previous Next →

Quicksort in other languages

• C