Quick Sort in C++ (Algorithm with Code Examples)

Quick sort is a divide and conquer sorting algorithm. It picks one element as a pivot, moves everything smaller than the pivot to its left and everything larger to its right, and then sorts the two sides the same way.

On average it runs in O(n log n) time, sorts in place with no extra array, and is the basis of the standard sort functions in many languages, including C++'s std::sort.

What Is Quick Sort?

Quick sort is a sorting algorithm that repeatedly partitions an array around a pivot element until every part is sorted. After one partition step, the pivot sits in its final sorted position, with smaller elements on its left and larger elements on its right. The algorithm then applies the same step to the left part and the right part, and the recursion ends when a part has one element or none.

Unlike merge sort, quick sort does not need a second array to merge into, which is why it is called an in-place sort.

How Does Quick Sort Work?

Every version of quick sort repeats the same four steps:

1. Choose a pivot element from the array, such as the last element.
2. Partition the array: move elements smaller than the pivot to its left and larger ones to its right. The pivot lands in its final position.
3. Recursively apply steps 1 and 2 to the subarray left of the pivot.
4. Recursively apply steps 1 and 2 to the subarray right of the pivot.

All the real work happens in the partition step. The two common partition schemes, Lomuto and Hoare, differ only in how they rearrange the elements.

Quick Sort in C++

1) Lomuto Partition Scheme

Lomuto partition uses the last element as the pivot and walks one index through the array, swapping every smaller element forward. It is the easiest scheme to write and trace:

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];      // last element as pivot
    int i = low - 1;            // boundary of the smaller side

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // place pivot in its final spot
    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);
    }
}

int main() {
    int arr[] = {24, 9, 29, 14, 19};
    int n = 5;

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    // Output: 9 14 19 24 29
    return 0;
}

2) Hoare Partition Scheme

Hoare partition uses two indexes that move toward each other from both ends, swapping out-of-place pairs. It does fewer swaps than Lomuto on average. Note the two differences: the pivot is the first element, and the recursive calls split at p and p + 1:

int partitionHoare(int arr[], int low, int high) {
    int pivot = arr[low];       // first element as pivot
    int i = low - 1, j = high + 1;

    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

void quickSortHoare(int arr[], int low, int high) {
    if (low < high) {
        int p = partitionHoare(arr, low, high);
        quickSortHoare(arr, low, p);      // note: p, not p - 1
        quickSortHoare(arr, p + 1, high);
    }
}

3) Randomized Pivot

A fixed pivot choice can meet its worst case: last-element pivots degrade to O(n²) on an already sorted array. Picking a random pivot makes that worst case extremely unlikely. Swap a random element into the pivot position, then partition as usual:

#include <cstdlib>

int partitionRandom(int arr[], int low, int high) {
    int r = low + rand() % (high - low + 1);
    swap(arr[r], arr[high]);    // random element becomes the pivot
    return partition(arr, low, high);
}

Quick Sort Example Step by Step

Here is the Lomuto version tracing {24, 9, 29, 14, 19}. The first partition takes 19 as the pivot, compares every other element with it, and swaps the smaller ones forward:

Compare	Action	Array after
24 vs 19	24 is larger, no swap	24 9 29 14 19
9 vs 19	9 is smaller, swap into position 0	9 24 29 14 19
29 vs 19	29 is larger, no swap	9 24 29 14 19
14 vs 19	14 is smaller, swap into position 1	9 14 29 24 19
end of pass	pivot swaps into position 2	9 14 19 24 29

After one partition, 19 is in its final place with {9, 14} on the left and {24, 29} on the right. Each side then gets its own pivot and partition, and since both sides here have two elements, one more round finishes the sort: 9 14 19 24 29.

Time and Space Complexity of Quick Sort

Case	Time	When it happens
Best	O(n log n)	Every pivot splits the array roughly in half
Average	O(n log n)	Random data, any reasonable pivot choice
Worst	O(n²)	Pivot is always the smallest or largest element, e.g. a sorted array with a last-element pivot

O(n log n) means the work grows only slightly faster than the array size, while O(n²) means doubling the array quadruples the work. Space complexity is O(log n) for the recursion stack in the average case, since the sort itself rearranges elements in place. Quick sort is not stable: equal elements can end up in a different relative order than they started.

Learn More About Quick Sort

Quick Sort in C

The algorithm is identical in C; only swap() needs to be written by hand:

#include <stdio.h>

void swapInts(int *a, int *b) { int t = *a; *a = *b; *b = t; }

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) swapInts(&arr[++i], &arr[j]);
    swapInts(&arr[i + 1], &arr[high]);
    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);
    }
}

int main() {
    int arr[] = {24, 9, 29, 14, 19};
    quickSort(arr, 0, 4);
    for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
    // Output: 9 14 19 24 29
    return 0;
}

Quick Sort vs Merge Sort

Both run in O(n log n) on average, and they trade different strengths. Quick sort works in place and is usually faster in practice thanks to cache-friendly memory access, but its worst case is O(n²) and it is not stable. Merge sort guarantees O(n log n) in every case and keeps equal elements in order, but needs O(n) extra memory for merging. Sorting libraries hedge the bet: std::sort in C++ uses introsort, which starts as quick sort and switches to heap sort if the recursion gets too deep.

When to Write Quick Sort Yourself

In production C++ code, std::sort(arr, arr + n) is the right call; it already contains an optimized quick sort. Writing the algorithm by hand matters for interviews and coursework, where partition tracing and complexity questions are standard. Simpler O(n²) algorithms like bubble sort are worth knowing for the same reason, as the usual baseline quick sort is compared against.

Key Takeaways for Quick Sort

• Divide and conquer - Pick a pivot, partition around it, and recurse on the two sides.
• The pivot lands in its final spot - Every partition places one element exactly where it belongs.
• O(n log n) average, O(n²) worst - The worst case hits when the pivot is always an extreme value; a randomized pivot avoids it.
• In place but not stable - No extra array is needed, and equal elements may swap relative order.
• Two partition schemes - Lomuto is simpler to write; Hoare does fewer swaps.
• Use std::sort in real code - It runs an optimized quick sort variant under the hood.

Partition-based sorting is one branch of the sorting family. On the other branch, insertion sort builds the sorted array one element at a time, and it is the algorithm quick sort implementations often switch to for tiny subarrays.