Algorithm Guidecomplexity: O(n log n)

Quick Sort

A fast, efficient divide-and-conquer algorithm that sorts by partitioning the array around a pivot. It underlies the built-in sort in most languages.

01Quick Sort

Explore How It Works

Starting quick sort. Pick one value as the pivot and drive everything smaller to its left, everything larger to its right.

Take the last value, 15, as the pivot. Now scan from the front for anything smaller than 15.

38 is larger than the pivot 15. It belongs on the right, so leave it alone.

27 is larger than 15 as well. Keep going.

43 is the same story. Nothing to send left yet.

Here is 10. It is smaller than 15, so it has to go to the left region.

Swap it with the 38 holding the first slot of the left region. 10 now stands on the left.

The last value, 76, is larger than 15 too. The scan is over.

The left region ended with just 10, so the pivot 15 belongs in the slot right after it.

Move 15 into that slot.

15 is now in its final place for good. Sort the left [10] and the right [43, 38, 76, 27] separately.

The left side holds only 10, so there is nothing left to do.

On to the right region. Take the last value, 27, as the pivot.

43 is larger than 27. Leave it.

38 is larger too. Move on.

76 and everything before it were larger than 27 — nothing goes to the left at all.

With the left region empty, 27 belongs at the very front of this region.

Move 27 into that slot.

27 has found its place too. Sort what remains, [38, 76, 43], the same way.

This time the last value, 43, is the pivot.

38 is smaller than 43, so it goes to the left region.

It already sits in the first slot on the left, so nothing has to move.

76 is larger than 43 and stays on the right.

One value, 38, went left, so 43 belongs right after it.

Move 43 into that slot.

Sorted · 10 15 27 38 43 76. Nailing one pivot at a time into its final place sorts the whole array.

Live Python

1def quick_sort(arr, low, high):

# low: 0, high: 5

2 if low < high:

3 pi = partition(arr, low, high)

4 quick_sort(arr, low, pi - 1)

5 quick_sort(arr, pi + 1, high)

7def partition(arr, low, high):

8 pivot = arr[high]

9 i = low - 1

10 for j in range(low, high):

11 if arr[j] <= pivot:

12 i += 1

13 arr[i], arr[j] = arr[j], arr[i]

14 arr[i+1], arr[high] = arr[high], arr[i+1]

15 return i + 1

1 / 26

02 Understand It Simply

For Everyone

🔑How It Works

Splits around a pivot into a smaller side and a larger side, then splits each side again. A consistently lopsided pivot degrades it to O(n²).

💡In Plain Words

Partitions values smaller than the pivot to the left and larger to the right, then sorts recursively.

Averages O(n log n) — very fast.

📍Where It's Used

–General-purpose sorting (most standard libraries)
–large datasets

03 Python Implementation

A clean, readable reference implementation of the core logic of Quick Sort.

core_implementation.py

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1