Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Quick sort

Explore the quick sort algorithm, a divide-and-conquer sorting method that partitions arrays around a pivot for efficient sorting. Understand its steps, pivot importance, and implementation details to improve practical coding skills and algorithmic efficiency.

We'll cover the following...

Imagine a teacher asks students to line up around a chosen benchmark height. Everyone shorter than the benchmark stands on the left, everyone taller than the benchmark stands on the right, and then each side repeats the process with its own benchmark.

That is the core idea of quick sort. Instead of merging sorted halves like merge sort, quick sort repeatedly partitions the array around a pivot element.

Quick sort is a divide-and-conquer sorting algorithm that chooses a pivot, partitions the array so smaller elements go left, and larger elements go right, then recursively sorts the two partitions.

Why it is called “quick”: On average, quick sort produces balanced partitions and sorts efficiently with low constant overhead. That is why it performs well in practice.

How it works

Quick sort usually has three conceptual steps:

  • Choose a pivot.

  • Partition the array so values smaller than the pivot move left and values larger move right.

  • Recursively sort the left and right partitions.

The partition step is the heart of the algorithm. Once the pivot lands in its correct final position, it never needs to move again.

Important: The algorithm’s speed depends heavily on pivot choice. Good pivots create balanced partitions. Bad pivots create uneven partitions and can cause worst-case performance.

Interactive animation

This visualizer focuses on the partition idea. It highlights the pivot and shows how smaller and larger values conceptually separate around it.

Algorithm

Before writing Python, read through the algorithm and connect each step to the trace above.

  1. If the list has one element or is empty:

    1. It is already sorted, so return.

  2. Otherwise:

    1. Choose a pivot element (commonly the last element).

    2. Partition the list around the pivot:

      1. Initialize a pointer i to track the boundary of smaller elements.

      2. Traverse the list from left to right (excluding the pivot):

        1. For each element:

          1. If it is smaller ...