Quick Sort Explained

Quick sort is a divide-and-conquer algorithm that sorts by picking a pivot element, partitioning the array so that smaller values go to the pivot's left and larger ones to its right, then recursively sorting each side. On average it runs in O(n log n) and sorts in place with very little extra memory, which makes it one of the fastest general-purpose sorts in practice — though a poorly chosen pivot can drag it down to O(n2).

The partition idea

The clever part of quick sort is partitioning. You choose a pivot, then rearrange the array so that everything less than the pivot sits before it and everything greater sits after it. After this single pass, the pivot is in its final sorted position — it will never move again. You then apply the same process to the left and right segments independently.

Because each partition correctly places one element and splits the rest into two smaller problems, repeated partitioning sorts the whole array.

Quick sort in C++

#include <iostream>
#include <vector>
using namespace std;

// Partition arr[low..high] around a pivot (the last element).
// Returns the pivot's final index. This pass is O(n) for the range.
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];   // choose the last element as pivot
    int i = low - 1;         // boundary of the "smaller than pivot" region

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]); // move smaller element into the left region
        }
    }
    swap(arr[i + 1], arr[high]);  // place pivot right after the smaller region
    return i + 1;                 // pivot is now in its final position
}

// Recursively sort arr[low..high]. Average O(n log n), worst case O(n^2).
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high); // pivot lands at index p
        quickSort(arr, low, p - 1);        // sort the left part
        quickSort(arr, p + 1, high);       // sort the right part
    }
}

int main() {
    vector<int> arr = {5, 2, 9, 1, 6, 3};
    quickSort(arr, 0, arr.size() - 1);
    for (int x : arr) cout << x << " "; // 1 2 3 5 6 9
    return 0;
}

Notice there is no temporary array — partitioning rearranges elements within the original array, which is why quick sort is in place.

Average versus worst case

When the pivot splits the array into two roughly equal halves, the recursion is log n deep and each level does O(n) partitioning work, giving the O(n log n) average. But if the pivot is always the smallest or largest element — which happens with the last-element pivot on already-sorted data — the partitions are maximally unbalanced (one element versus the rest), the recursion becomes n deep, and the cost balloons to O(n2).

Avoiding the worst case

The fix is choosing a better pivot:

• Randomised pivot — pick a random element, making the worst case astronomically unlikely for any fixed input.
• Median-of-three — pick the median of the first, middle, and last elements, which handles sorted and reverse-sorted inputs well.

These strategies keep quick sort fast on real-world data. This is the key difference from merge sort, which guarantees O(n log n) but always uses O(n) extra space.

Quick sort versus merge sort

Quick sort is usually faster in practice due to good cache behaviour and low overhead, and it is the common default for in-memory array sorting. Choose merge sort when you need the guaranteed worst case or stability.

Common mistakes

• Always picking a fixed pivot. A last-element (or first-element) pivot turns sorted input into the O(n2) worst case. Randomise or use median-of-three.
• Off-by-one in partition bounds. The recursive calls must exclude the pivot: low..p-1 and p+1..high. Including the pivot can loop forever.
• Forgetting the base case. The if (low < high) guard stops the recursion on segments of size zero or one. Omitting it overflows the stack.
• Expecting stability. The swaps in partitioning can reorder equal elements. If you need stable sorting, use merge sort.
• Worrying only about average. For adversarial or already-sorted data, the naive version is genuinely O(n2). Always pivot defensively in production code.

FAQ

Why is quick sort often faster than merge sort despite the worse worst case? It sorts in place with excellent cache locality and low constant overhead, so on typical data with a good pivot it usually beats merge sort in real running time.

Is quick sort stable? Not in its standard form — partitioning can swap equal elements out of order. Use merge sort when stability is required.

Keep learning

Compare it directly with Merge Sort, revisit the recursion patterns it depends on, and browse the full DSA hub.

Want to implement quick sort and pivot strategies with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.