Quick Sort Algorithm Explained with Examples

By Khaled Md Tuhidul Hossain · 2025-05-22 · Algorithms

Quick Sort is one of those algorithms that looks intimidating until you actually trace through it. The core idea is surprisingly elegant: pick an element, put everything smaller to its left and everything bigger to its right, then do the same thing for the left and right halves. That's it.

What makes it special is how efficient this turns out to be in practice. On average, it runs in O(n log n) time and sorts in-place, which is why languages like C, Java, and Python use variations of it under the hood.

Interactive visualization

Use the controls below to step through the algorithm or let it play automatically.

name: quick-sort
input: [8, 3, 1, 7, 0, 10, 2]
speed: 500

How Quick Sort works

The algorithm follows a divide-and-conquer strategy with three steps:

1. Pick a pivot. Choose an element from the array. There are different strategies for this, and your choice matters more than you'd think.
2. Partition. Rearrange the array so all elements smaller than the pivot go to its left, and all elements larger go to its right. After this step, the pivot is in its final sorted position.
3. Recurse. Apply the same process to the left and right subarrays.

Here's the overall flow:

The partition step in detail

This is where the real work happens. Let's use the Lomuto partition scheme since it's easier to follow. We pick the last element as the pivot and walk through the array with two pointers.

Step-by-step walkthrough

Let's sort [8, 3, 1, 7, 0, 10, 2] and trace through the whole process.

First call: partition the full array

Pivot = 2 (last element)

Array: [8, 3, 1, 7, 0, 10, 2]
                            ^ pivot = 2

i starts at -1, j walks left to right:

j=0: arr[0]=8 > 2, skip
j=1: arr[1]=3 > 2, skip
j=2: arr[2]=1 <= 2, i=0, swap arr[0] and arr[2]
     → [1, 3, 8, 7, 0, 10, 2]

j=3: arr[3]=7 > 2, skip
j=4: arr[4]=0 <= 2, i=1, swap arr[1] and arr[4]
     → [1, 0, 8, 7, 3, 10, 2]

j=5: arr[5]=10 > 2, skip

Final swap: put pivot at i+1=2
     → [1, 0, 2, 7, 3, 10, 8]
              ^ pivot is now at index 2 (its correct position!)

So now we have:

• Left subarray: [1, 0] (everything less than 2)
• Pivot: 2 (in its final spot)
• Right subarray: [7, 3, 10, 8] (everything greater than 2)

Sorting the left subarray: [1, 0]

Pivot = 0

j=0: arr[0]=1 > 0, skip
Final swap: put pivot at index 0
     → [0, 1]

Both elements are in place. Done with the left side.

Sorting the right subarray: [7, 3, 10, 8]

Pivot = 8

j=0: arr[0]=7 <= 8, i=0, no swap needed (already in position)
j=1: arr[1]=3 <= 8, i=1, no swap needed
j=2: arr[2]=10 > 8, skip

Final swap: put pivot at i+1=2
     → [7, 3, 8, 10]
              ^ pivot at correct position

Now recurse on [7, 3] and [10].

[7, 3] with pivot = 3:

j=0: arr[0]=7 > 3, skip
Final swap: → [3, 7]  ✓

[10] is a single element, so it's already sorted.

Final result

Combining everything: [0, 1, 2, 3, 7, 8, 10]

Python implementation

Here's a straightforward implementation:

def quick_sort(arr):
    """Sort an array using Quick Sort (in-place)."""
    _quick_sort(arr, 0, len(arr) - 1)
    return arr


def _quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        _quick_sort(arr, low, pivot_index - 1)
        _quick_sort(arr, pivot_index + 1, high)


def partition(arr, low, high):
    """Lomuto partition: use last element as pivot."""
    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

Now here's a version with randomized pivot selection, which avoids worst-case behavior on already-sorted input:

import random


def quick_sort_randomized(arr):
    """Quick Sort with random pivot to avoid worst-case patterns."""
    _qs_random(arr, 0, len(arr) - 1)
    return arr


def _qs_random(arr, low, high):
    if low < high:
        pivot_index = randomized_partition(arr, low, high)
        _qs_random(arr, low, pivot_index - 1)
        _qs_random(arr, pivot_index + 1, high)


def randomized_partition(arr, low, high):
    """Pick a random pivot and partition around it."""
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return partition(arr, low, high)


# Try it out
numbers = [8, 3, 1, 7, 0, 10, 2]
print(f"Before: {numbers}")
quick_sort_randomized(numbers)
print(f"After:  {numbers}")

Output:

Before: [8, 3, 1, 7, 0, 10, 2]
After:  [0, 1, 2, 3, 7, 8, 10]

Pivot selection strategies

Your choice of pivot can make or break performance. Here's what you should know:

Last element (Lomuto). Simple to implement, but terrible on already-sorted arrays because every partition is maximally unbalanced. You get O(n²) on sorted input, which is ironic for a sorting algorithm.

Random element. Swap a random element to the end and use Lomuto as usual. This makes worst-case behavior extremely unlikely. In practice, this is often good enough.

Median of three. Pick the first, middle, and last elements. Use the median of those three as the pivot. This gives consistently good partitions and is what most production implementations use.

Time and space complexity

The O(log n) space comes from the recursion stack. In the worst case (already sorted array with last-element pivot), the stack depth hits O(n), which can cause a stack overflow on large inputs. Randomized pivots fix this in practice.

When should you use Quick Sort?

Quick Sort is the workhorse of sorting algorithms. Here's where it really shines:

General-purpose sorting. When you need to sort data and don't have a specific reason to pick something else, Quick Sort is usually the right call. Its average-case O(n log n) with low constant factors makes it faster than Merge Sort in practice for most inputs.

In-place sorting when memory matters. Unlike Merge Sort which needs O(n) extra space, Quick Sort works in-place. If you're sorting millions of records and can't afford to double your memory usage, this is a big deal.

Competitive programming. Speed matters in contests. Quick Sort's cache-friendly access patterns and low overhead make it consistently fast. Just use randomized pivots so you don't get tripped up by adversarial test cases.

Real problem examples

1. Database query results. When a database engine sorts rows for an ORDER BY clause, it often uses a variant of Quick Sort. The in-place nature means less memory pressure when sorting millions of rows.

2. Sorting files by size or date. File managers need to sort thousands of files quickly. Quick Sort handles this well because the data is rarely adversarial, and the average case is fast.

3. Preprocessing for binary search. You need your data sorted before you can binary search it. Quick Sort gets you there in O(n log n) with minimal extra memory, which is exactly what you want when the dataset is large.

4. Partitioning problems. Even if you don't need a full sort, the partition step alone solves the "Dutch National Flag" problem and the "Kth smallest element" problem (using Quickselect, which is Quick Sort's cousin).

Quick Sort vs other sorting algorithms

So when would you pick something else? If you need a stable sort (equal elements keep their original order), go with Merge Sort. If you're sorting linked lists, Merge Sort is also better since Quick Sort relies on random access. And if you need guaranteed O(n log n) worst case, Heap Sort has that, though it's slower in practice.

But for arrays with random-ish data where stability doesn't matter, Quick Sort is hard to beat. There's a reason it's been the default choice for decades.

Wrapping up

Quick Sort is fast, practical, and elegant once you get the partition step down. The main thing to watch out for is pivot selection. Use randomized pivots or median-of-three, and you'll avoid the O(n²) worst case in any realistic scenario.

If you only learn one sorting algorithm deeply, make it this one. It shows up in interviews, it powers real systems, and the divide-and-conquer thinking behind it applies to tons of other problems.