Python Algorithms

Quick Sort in Python

Pick a pivot, split the list into smaller, equal and larger parts, and sort each part the same way.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • Choosing a pivot
  • Partitioning with list comprehensions
  • Average O(n log n) versus worst-case O(n²)
Pivot 9 (the middle value) in [10, 7, 8, 9, 1, 5]
lower
[7, 8, 1, 5]
  • sort again
equal
[9]
  • already in place
higher
[10]
  • one value: done

Partition around a pivot

The problem

Quicksort is one of the most widely used sorting ideas because it is fast on average and easy to express. It shows another way to divide a problem: instead of splitting in the middle, split around a chosen value.

Think of it like this

Quicksort is like sorting books by height around one chosen book. Put every shorter book on the left pile, every taller book on the right pile and books of the same height in the middle. Then sort each side pile the same way, and put the piles back together.

From piles of books to code
pivot = values[len(values) // 2]📕 Choose one book to compare against
lower = [... if value < pivot]⬅️ Shorter books to the left
higher = [... if value > pivot]➡️ Taller books to the right
quick_sort(lower) + equal + quick_sort(higher)📚 Sort each side, then join the piles
Partition around a pivot, then sort each side the same way.
In one sentence

Quicksort picks a pivot, splits the other items into those smaller and larger than it, sorts each part recursively and joins them, taking O(n log n) time on average.

Key points

  1. if len(values) <= 1: is the base case: such a list is already sorted.
  2. pivot = values[len(values) // 2] takes the middle value as the pivot.
  3. lower, equal and higher split the values around the pivot; equal keeps duplicates together.
  4. quick_sort(lower) + equal + quick_sort(higher) sorts the two sides and joins the three lists.

When should you use it?

  • Learning partitioning and recursion.
  • General-purpose in-place sorting in languages and libraries (with careful pivot choice).
  • Selection problems such as finding the median (quickselect uses the same partition).

When not to use it

  • Normal Python code: sorted() is faster and stable.
  • When a guaranteed worst case matters: bad pivots make quicksort O(n²); merge sort never is.

Quick Sort in Python visualizer

O(n log n)

Use Play or Step to follow each comparison and data movement.

Example code

Run code →
main.py
def quick_sort(values):
    if len(values) <= 1:
        return values
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

print(quick_sort([10, 7, 8, 9, 1, 5]))
Get a Run button for this example

Result of running the code

[1, 5, 7, 8, 9, 10]

Code explanation

This readable version creates three partitions. Average time complexity is O(n log n), although poor pivot choices can produce O(n²).

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Dropping values equal to the pivot

With only < and >, duplicates of the pivot disappear.

Problem
return quick_sort(lower) + [pivot] + quick_sort(higher)
Fix
return quick_sort(lower) + equal + quick_sort(higher)

Finished this lesson?

Mark it as learned to track your progress.

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges