Editor

Quick sort in Python

Quick sort picks a pivot, moves the smaller values to its left and the rest to its right, then sorts the two sides the same way. The partition happens in place, inside the list itself.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. partition takes the last value of the range, nums[high], as the pivot.
  2. j walks from low to just before the pivot. Every value smaller than the pivot is swapped to position i, and i moves one step right.
  3. Finally the pivot is swapped into position i: everything left of it is smaller, everything right of it is bigger or equal.
  4. The pivot is now in its final place, so quick_sort calls itself on the part left of it and the part right of it.
  5. A range with fewer than two values (low >= high) is already sorted, so the recursion stops there.

What to watch

  • Watch i mark the end of the "smaller than the pivot" zone while j scans ahead of it.
  • Watch the last swap of each partition drop the pivot bar into its final position.
  • Watch the call stack: every quick_sort call works on a smaller range than the one that called it.

The code

def partition(nums, low, high):
    pivot = nums[high]       # the last value is the pivot
    i = low                  # next place for a value smaller than the pivot
    for j in range(low, high):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[high] = nums[high], nums[i]   # pivot goes between the parts
    return i

def quick_sort(nums, low, high):
    if low < high:
        p = partition(nums, low, high)
        quick_sort(nums, low, p - 1)    # values smaller than the pivot
        quick_sort(nums, p + 1, high)   # values bigger or equal

data = [7, 2, 9, 4, 1, 6]
quick_sort(data, 0, len(data) - 1)
print(data)
Output
[1, 2, 4, 6, 7, 9]

Open it in the editor · Python Program for Quick Sort, explained