Python Program for Quick Sort

Sorts a list in place by moving smaller items before a pivot and the rest after it, then sorting each side: O(n log n) time on average.

Quick sort is built on one step, the partition: pick an item, the pivot, and rearrange the list so that the items smaller than it come before it and the rest after it. The pivot is then in its final place, and each side is sorted the same way. With 10 as the pivot, [38, 27, 43, 3, 9, 82, 10] becomes [3, 9, 10, 38, 27, 82, 43]: 10 is in place, and the items on either side of it are sorted separately.

This program uses the Lomuto partition, with the last item as the pivot. It moves items around inside the list itself, without building new lists, which is what makes quick sort fast in practice, and it's the version exams and interviews ask for. A shorter version that builds new lists is under "Other ways to write it".

Program

def quick_sort(items, low=0, high=None):
    """Sort items[low:high + 1] in place, smallest first."""
    if high is None:
        high = len(items) - 1
    if low < high:
        p = partition(items, low, high)
        quick_sort(items, low, p - 1)   # the items before the pivot
        quick_sort(items, p + 1, high)  # the items after it


def partition(items, low, high):
    """Put the pivot, items[high], in its sorted place; return it."""
    pivot = items[high]
    i = low  # where the next item smaller than the pivot goes
    for j in range(low, high):
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]
    return i


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
quick_sort(numbers)
print("After: ", numbers)

Open in the editor Download quick_sort.py

Output

Before: [38, 27, 43, 3, 9, 82, 10]
After:  [3, 9, 10, 27, 38, 43, 82]

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. The first call sorts the whole list: low is 0 by default, and high becomes the last index. The calls the function makes to itself pass both, to sort one part of the list.
2. A part with fewer than two items is already sorted, so there's nothing to do. This is the base case that stops the recursion.
3. partition rearranges the part around its pivot and returns p, the pivot's final index.
4. The function sorts the items before the pivot and the items after it. The pivot itself never moves again.
5. The pivot is the last item of the part. i marks where the next item smaller than the pivot will go, so everything before i is smaller than the pivot.
6. The loop looks at every other item in the part. Each one smaller than the pivot swaps to index i, and i moves on by one.
7. Last, the pivot swaps into index i, right after the smaller items, so everything after it is at least as big. The function returns that index.
8. The program prints the list, sorts it in place, and prints it again.

The first partition, with 10 as the pivot:

Then 10 swaps into index 2, giving [3, 9, 10, 38, 27, 82, 43], and partition returns 2. The whole sort takes four partitions:

Time and space complexity

When each pivot lands near the middle of its part, every split halves the work: there are about log₂ n levels of splits, and each level compares every item with a pivot once. That's O(n log n) time, the average case for a list in no particular order, and the calls go about log₂ n deep, so the extra space is O(log n). The worst case comes when every pivot is the smallest or largest item of its part. Each split then sets aside only the pivot, so the sort takes n − 1 levels and O(n²) time, and the calls go n deep, which is O(n) space. With the last item as the pivot, that happens on a list that is already sorted, or sorted in reverse: a sorted list of 1,000 items is enough to reach Python's limit on nested calls. Taking the middle item as the pivot avoids that case. Quick sort is not stable: a swap can carry an item past an equal one.

Other ways to write it

With list comprehensions

This version is the shortest to read: it splits the list into three new lists around the middle item and joins the sorted parts (list comprehensions). It returns a new list and needs O(n) extra space, so it gives up sorting in place, but it shows the idea in a few lines.

def quick_sort(items):
    if len(items) <= 1:
        return 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)

print(quick_sort([38, 27, 43, 3, 9, 82, 10]))

Try it yourself

• Print low, high and the pivot at the start of each partition call, and compare them with the table above.
• Sort a list that's already sorted, such as [3, 9, 10, 27, 38, 43, 82], and count the partition calls: 6, as each one sets aside only its pivot.
• Use the middle item as the pivot: at the start of partition, swap items[(low + high) // 2] with items[high]. Sort the sorted list again: it now takes 3 calls.
• Sort from largest to smallest by changing one comparison.

More searching and sorting programs

• Python Program for Bubble Sort Beginner
• Python Program for Insertion Sort Beginner
• Python Program for Linear Search Beginner
• Python Program for Selection Sort Beginner
• Python Program for Binary Search Intermediate
• Python Program for Merge Sort Intermediate