Quick Sort Step by Step With a Worked Example

Quick sort is the sort real programs actually use. It is fast, it sorts in place, and it shows up in coding interviews all the time. But the way it works confuses people, because two ideas run at once. A split, and a repeat.

Let me slow it down. Once you watch a single pivot lock into place, the rest is just the same trick over and over.

What is quick sort?

Quick sort is a sorting method that works by splitting the array around a chosen value. That chosen value is called the pivot. Every value smaller than the pivot moves to its left. Every value larger moves to its right.

Once that split is done, the pivot sits in the exact place it belongs in the final sorted list. It never has to move again. That is the whole magic. One pass puts one value home for good.

Then quick sort does the same thing to the smaller pieces on each side. It keeps splitting until every piece is a single value. A single value is already sorted, so the work stops there. Quick sort is much faster than simple sorts like selection sort on real data.

How does quick sort work step by step?

Reading the steps is not enough. You have to watch the values move. So let’s run quick sort on a real array and follow the pivot.

Take the array [6, 2, 8, 4, 3]. We will use the last value, 3, as our pivot.

Quick sort walks through the other values and sorts them around the pivot. Only 2 is smaller than 3. The values 6, 8 and 4 are all larger. So after this first pass the array becomes [2, 3, 6, 8, 4]. The pivot 3 has landed in its final resting place at the second spot.

That pivot is now done for good. Everything to its left is smaller. Everything to its right is larger. So quick sort splits the work in two. It handles the left part [2] and the right part [6, 8, 4] on their own.

The left part is just [2], so it is already sorted. The right part [6, 8, 4] gets the same treatment. Pick the last value, 4, as the pivot. Nothing in 6 and 8 is smaller than 4, so 4 moves to the front and the part becomes [4, 6, 8]. Now 4 is locked in place too. That leaves [6, 8], which sorts in one more tiny step. The whole array is now [2, 3, 4, 6, 8].

What is a pivot and how do you pick one?

The pivot is the value quick sort splits around. The choice of pivot matters more than beginners expect. A good pivot lands near the middle of the values, which splits the array into two halves of roughly equal size. That balance is what keeps quick sort fast.

Common choices are the last value, the first value, the middle value, or a random one. Using the last value is the simplest to code, so most courses teach it first. But it has a weakness. If the array is already sorted, the last value is the largest, and the split is badly lopsided. A random pivot avoids that trap, because no single input can fool it every time.

Quick sort code in Python and C++

Quick sort needs two parts. A partition step that does the splitting, and a main function that calls itself on each half. Here it is in Python.

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

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

The partition function does the heavy lifting. It pushes smaller values to the front then drops the pivot into the gap. The main function then sorts the part before the pivot and the part after it.

Here is the same logic in C++, the language most Indian placement tests expect.

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
    int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

Both versions follow the same plan. Partition once, then sort each side. The recursion stops on its own when a part has one value or none.

What is the time and space complexity of quick sort?

On average, quick sort runs in O(n log n) time. A good pivot cuts the array in half each round, and there are only about log n rounds. That is why it is one of the fastest sorts in everyday use.

The worst case is the catch. If the pivot is always the smallest or largest value, the split removes only one item each round instead of half. That drops quick sort all the way down to O(n²), the same speed as the slow simple sorts. An already sorted array with a last-value pivot triggers this exact problem.

The size of that gap is huge. Sorting a million items the average way takes about 20 million comparisons. The worst case balloons to around a trillion. So picking a smart pivot is not a small detail. It is the difference between instant and frozen.

Space stays small. Quick sort rearranges values inside the original array, so it needs no second array. The only extra memory is the recursion stack, which is about O(log n). One more thing to know. Quick sort is not stable, so equal values can swap their original order. You can check the formal definition on Wikipedia’s quicksort page.

Quick sort vs merge sort

Quick sort and merge sort are the two famous fast sorts, and both average O(n log n). The difference is the trade-off. Quick sort sorts in place with little extra memory but has that ugly O(n²) worst case. Merge sort always stays at O(n log n) and is stable, but it needs extra memory to do it. For the full comparison, read our merge sort walkthrough.

FAQ

Why is quick sort called quick?

Because on average it is one of the fastest sorts in real use. It runs in O(n log n) time and sorts in place, so it moves data efficiently without needing a second array.

What is the worst case of quick sort?

O(n²), which happens when the pivot is always the smallest or largest value. An already sorted array with a last-value pivot is the classic trigger. A random or middle pivot avoids it.

Is quick sort stable?

No. Equal values can change their original order during partitioning. If you need stability, merge sort is the better pick.

Does quick sort use extra memory?

Very little. It sorts inside the original array, so the only extra space is the recursion stack, which is about O(log n) on average.

Which pivot should I choose?

For learning, the last value is the simplest. For real code, a random pivot or the middle value is safer, because it dodges the O(n²) worst case on sorted input.

Is quick sort better than merge sort?

It depends. Quick sort is usually faster in practice and uses less memory. Merge sort is more predictable and stable. Pick quick sort for speed and merge sort when stability or a guaranteed O(n log n) matters.

So what should you remember?

Quick sort works by trust. Pick a pivot, split the array around it, and that pivot is home for good. Then repeat on each half until the pieces are too small to split.

The pivot choice is everything. A balanced split keeps it fast. A lopsided one drags it down to the speed of the sorts you were trying to leave behind.

Now try it on [9, 1, 5, 3, 7] using the last value as the pivot. Where does the first pivot land?