Quick sort

Why it matters

Quick sort is one of the fastest general-purpose sorts in practice, and it is one of the most common interview topics. Its central step, partitioning, does more than sorting. It also solves "find the k-th largest element" problems, and it teaches a lesson about worst cases that every serious programmer needs to know.

By the end of this lesson you will partition an array by hand, write quick sort in C++, explain why a bad pivot choice makes it slow, and use quickselect to find a value without sorting everything. You will also see why quick sort is not stable, and how to handle many equal values.

The idea: put the pivot in its place first

Merge sort does its real work after the recursive calls, when it merges two sorted halves. Quick sort does the work before the recursive calls. It picks one value, called the pivot, and rearranges the array so that every smaller value sits to the left of the pivot and every bigger value sits to the right. This rearrangement is called partitioning.

Here is an analogy. Imagine a class of students standing in a line by height, and you need them sorted. You pick one student at random and ask everyone shorter to step to the left and everyone taller to step to the right. The chosen student is now standing in the place where they belong. Nobody on the left is taller, and nobody on the right is shorter. You then repeat the same process inside the left group and inside the right group.

After one partition, the pivot is in its final sorted position, and it will never move again. The left part and the right part are not sorted yet, but each one is smaller than the pivot and bigger than the pivot, so the problem has been split into two smaller problems. That is divide and conquer with the work done up front.

Quick sort has three steps.

1. Partition the range around a pivot. Put the pivot in its final place.
2. Recurse on the left part, the values smaller than the pivot.
3. Recurse on the right part, the values bigger than the pivot.

There is no combine step. When both parts are sorted, the whole array is sorted, because the pivot already sits between them.

One partition step, slowly

There are several ways to partition. This module uses the Lomuto scheme, which is easy to follow. Lomuto uses the last value in the range as the pivot. It keeps one index, i, which marks the next free slot for a small value. It walks through the range with j. Whenever a[j] is smaller than the pivot, it swaps a[j] into the slot at i and moves i forward. At the end, the pivot is swapped into slot i.

Take the array 10 7 8 9 1 5. The pivot is the last value, 5. The table shows each step.

After the last step, the pivot 5 sits at index 1. Everything to its left is smaller than 5, which is just the value 1. Everything to its right is bigger than 5. The partition function returns the index 1, so the caller knows where the pivot is.

The diagram shows the same array after each important swap.

One Lomuto partition of 10 7 8 9 1 5 with pivot 5, showing the swap that moves 1 to the front and the final swap that places the pivot

Now run the partition by itself. The program below reads an array, partitions it using the last value as the pivot, and prints the result and the pivot index.

Press Run and type this in the Input box:

6
10 7 8 9 1 5

The output is:

1 5 8 9 10 7
pivot index 1

The output matches the table. The array is not sorted. The values on each side of the pivot are not sorted either. Only the pivot is in its final place. That is all one partition promises, and the recursion does the rest.

Quick sort: partition, then recurse

The quick sort function is short. It calls partition on the range, then calls itself on the two parts on either side of the pivot. The pivot index is excluded from both calls, because it is already in its final place.

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;              // zero or one value: already sorted
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

The base case is the same as in merge sort: a range with zero or one value. Watch the arithmetic in the two recursive calls. The left call stops at p - 1 and the right call starts at p + 1. If you wrote quickSort(a, lo, p) instead, the same pivot would be included again, and the range would never shrink in some cases, causing an infinite loop.

The visualizer below runs the whole process, one partition at a time. Watch the pivot turn into a fixed value after each partition, and watch the ranges on each side get smaller.

Quick sort is the usual choice when speed on typical data matters and memory is tight. It sorts in place, so it does not need a second array the size of the input. Its recursion depth is usually about log n. The cost depends on how evenly each partition splits the range, which is the subject of the next section.

Pick a better pivot

If every partition splits the range into two equal halves, there are log n levels, and each level does about n work. That gives O(n log n) time, the same as merge sort. The question is how to get balanced splits.

The Lomuto scheme uses the last value as the pivot. If the input is random, that value is a typical value, so the split is usually reasonable. If the input is already sorted, the last value is the biggest value. Then every partition puts the pivot at the far right, and the left part holds everything else. The split is as unbalanced as possible. The next section shows the cost.

A common fix is median of three. Look at three values: the first, the middle and the last. Put them in order, so that the first is smallest and the last is biggest. The middle of the three is the median. Move that median to the last position and partition with it. On sorted data the first value is the smallest, the last value is the biggest, and the middle value is the median. So the median of three is always the middle value. That gives a balanced split for sorted input.

The next program uses median of three. It reads an array, sorts it with the improved quick sort, and prints the result.

Type this in the Input box, and press Run:

8
5 1 9 3 7 2 8 6

The output is:

1 2 3 5 6 7 8 9

The function medianOfThreeToEnd does not sort the whole range. It only places three values so that the median is at hi. That is enough for the partition to work well. Notice that the code uses a[mid] and a[hi] with swap calls in a fixed order. The order of the three swaps is what makes the result the median. Changing the order can leave a value that is not the median in the pivot slot, which still sorts correctly but loses the balanced split.

The worst case, measured

Now the worst case becomes concrete. The next program counts comparisons. A comparison is one check of a[j] < pivot inside the partition. It sorts the numbers 1 to n, which are already sorted, in two ways: once with the last value as the pivot, and once with median of three. The input is 1000.

Type 1000 in the Input box and press Run. The output is:

last element as pivot: 499500 comparisons
median of three: 7987 comparisons

The first number is exact. With the last value as pivot, each partition of a range of size m makes m - 1 comparisons and puts the pivot at the far right. The ranges are 1000, 999, 998 and so on down to two values. The total is 999 + 998 + ... + 1, which is 1000 * 999 / 2, or 499500. For 1000 values that is about 500 times the work of a balanced sort.

The second number is much smaller, 7987. With median of three, the splits are balanced, so the work is about n log n, which is 10000 for n = 1000. The exact count is slightly smaller than the rough estimate because the last levels have fewer values.

The picture below shows the bad case as a sequence of partitions. Each level places only one value, and the rest of the work falls on the one remaining part.

Quick sort on sorted input with the last value as pivot, where each level places only the pivot and the whole rest goes to one side

The lesson to take from this is simple. Quick sort is fast on average, but its worst case is O(n squared), which means work that grows with the square of the input. The worst case is not rare for structured inputs such as sorted or nearly sorted data, which are common in real systems. You must guard against it with a better pivot choice or with randomness.

Random pivots

Another defence is to choose the pivot at random. Swap a random position in the range with the last position, and then partition as usual. An adversary who does not know your random choices cannot build an input that is slow every time. The expected cost on any input becomes O(n log n), although a single unlucky run can still be slow.

#include <random>
mt19937 rng(12345);
 
void quickSortRandom(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int r = uniform_int_distribution<int>(lo, hi)(rng);
    swap(a[r], a[hi]);                 // random pivot moved to the end
    int p = partition(a, lo, hi);
    quickSortRandom(a, lo, p - 1);
    quickSortRandom(a, p + 1, hi);
}

The mt19937 generator is a standard random number source in C++. Setting a fixed seed like 12345 makes the program repeatable, which is useful for tests and for debugging. For a real program you would seed it with random_device or the clock. The result is the same sorted array either way, but the order of partitions differs.

Median of three and random pivots are both good choices. Many library sorts use a mix of the two, with a fallback to a different algorithm when the recursion goes too deep. You do not need that detail for this module. You do need to know that a fixed rule like "always use the last value" is unsafe on structured input.

Quickselect: the k-th smallest without a full sort

Sometimes you do not need the whole array sorted. You may only need the 3rd smallest score, or the median, or the 10 largest values. Sorting everything would do more work than needed. Quickselect uses the partition step to answer this kind of question faster.

After one partition, the pivot is at its final index p. Its index tells you its rank. If p equals the position you want, the pivot is the answer. If the position you want is smaller than p, the answer lies in the left part, so you recurse only on the left. If it is bigger, you recurse only on the right. Half of the work is thrown away each time, on average.

The next program uses quickselect to find the k-th smallest value. It reads n and k, then n values, and prints the value at place k. Place 1 is the smallest value.

Type this in the Input box, and press Run:

6 3
7 10 4 3 20 15

The output is 7. In sorted order the values are 3 4 7 10 15 20, and the third smallest is 7.

Trace the first partition. The pivot is 15, the last value. The values smaller than 15 are 7, 10, 4 and 3, and they are moved to the front, in some order. The pivot lands at index 4, because four values are smaller. The target place is index 2 (0-based), which is on the left of 4. So the search continues on the left part, 7 10 4 3, with the same target. The next partition finishes the job.

The cost is linear on average. The first pass looks at n values, the second at about n / 2, the third at about n / 4, and so on. The sum is about 2n, which is O(n). That is much better than sorting, which costs O(n log n). The worst case is still O(n squared), for the same reason as quick sort, so random pivots are used in serious implementations.

Duplicates and three-way partition

Quick sort has one more trap, and it is common in real data: many equal values. The Lomuto partition sends every value that is smaller than the pivot to the left, and every value that is not smaller to the right. Equal values go to the right, together with the bigger values. If every value is equal, the right part always holds all the other values, and the split is as unbalanced as possible.

Test it in your head with eight equal values. The first partition moves nothing, the pivot lands at the start, and the right part has seven values. The next partition does the same to seven values, then six, and so on. The number of comparisons is 7 + 6 + ... + 1, which is 28, the same pattern as the sorted case. With a thousand equal values you would get about 500000 comparisons.

The fix is a three-way partition. It splits the range into three parts: smaller than the pivot, equal to the pivot, and bigger than the pivot. The equal part is already in its final place, so the recursion does not have to visit it. The idea is also called the Dutch national flag partition, because it sorts three colours in one pass.

void quickSort3(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo + (hi - lo) / 2];
    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot) swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else i++;
    }
    quickSort3(a, lo, lt - 1);
    quickSort3(a, gt + 1, hi);
}

The three parts are lo to lt - 1 for smaller values, lt to gt for equal values, and gt + 1 to hi for bigger values. The loop moves values into the correct part as it scans. When a value is bigger, it swaps it with the one at gt and shrinks the scan from the right, but it does not move i, because the swapped-in value has not been checked yet. That detail is the most common bug in this function, so write it out on paper once.

Quickselect needs the same change. Without it, the k-th smallest among many equal values can take quadratic time. The practice exercises ask you to add it.

Quick sort is not stable

Recall the stability idea from the previous lesson. A stable sort keeps equal items in their original order. Quick sort does not, and you can see why by looking at a swap. Take the array 2a 2b 1, where 2a and 2b are two items with the same key 2, and 2a comes first. The pivot is 1, the last value. Nothing is smaller than 1, so i stays at 0. The loop does nothing, and the final swap exchanges a[0] with the pivot. The array becomes 1 2b 2a. Now 2b comes before 2a, and their original order is gone.

Merge sort keeps equal items in order because it never jumps an item over another equal item. Quick sort jumps items across the array to build the partition, and those jumps can reverse equal items. When stability matters and the data is an array of records, use merge sort, or a stable library sort. If you do not need stability, quick sort's speed and low memory use make it a strong choice.

Complexity summary

The table shows the trade-off. Quick sort is fast and uses little memory, but its guarantee depends on the pivot choice. Merge sort gives a guarantee and stability, at the cost of an extra array.

Common mistakes

Forgetting the final swap. Without swap(a[i], a[hi]), the pivot is never placed. The result looks partly sorted, and the partition returns an index that does not match the pivot. Print the array after each partition to catch this.

Using p instead of p - 1 or p + 1 in the recursive calls. The pivot is already in place, so including it wastes work. Worse, using p on the right side can make the range stop shrinking, which repeats the same call forever.

Using <= on one side and < on the other. Mixing the two conditions can give uneven splits when values are equal, and in some versions it makes the loop run past the end of the range. Pick one convention and keep it.

Recursing on the whole range when only one side is needed. Quickselect must recurse on one side only. Recursing on both sides turns it into a full sort, and the algorithm loses its linear average.

Using a fixed pivot on structured data. Sorted input, reversed input and input with many equal values can all trigger the worst case. Use median of three, a random pivot, or a three-way partition.

Deep recursion on bad input. When the pivot is always the largest value, the recursion depth is about n, and each level keeps a stack frame. A very large input can exhaust the stack. Recursing on the smaller side first, or using a loop with an explicit stack, keeps the depth to about log n.

Debugging a quick sort

Quick sort bugs are usually visible in one partition. When the output is wrong, print the array and the pivot index for the first call, then check the partition by hand. The partition is correct when everything left of the pivot is smaller, everything right of it is bigger or equal, and the pivot is at the returned index.

Use the partition program from this lesson. Remove the final swap line and run the same input with 6 and 10 7 8 9 1 5. The output becomes 1 7 8 9 10 5 with pivot index 1, because the pivot never moved. The function says the pivot is at index 1, but the value there is 7, not 5. The 5 is still at the end of the array, on the wrong side of the values that are bigger than it. This is a small example that shows the bug, and it is easy to spot once you know what to look for.

For a performance bug, count comparisons, as in the median-of-three program. A count that is much bigger than n log n means the splits are unbalanced. Check the pivot rule first.

Hoare partition in one paragraph

Lomuto is the easiest partition to follow, but it does more swaps than necessary when values repeat. Many production sorts use Hoare's partition instead. It keeps two indexes, one moving in from the left and one moving in from the right. Each index stops when it finds a value that belongs on the other side, and the two values are swapped. The scan ends when the indexes cross. Equal values stop both scans, so they are split evenly between the two sides, which helps with many duplicates. Its end point differs slightly, so the recursion uses ranges that include the pivot position. You do not need Hoare's version for this module, but you should know that it exists, and that interviewers may ask how it differs from Lomuto.

Edge cases for quick sort

An empty array or a single value needs no work. The base case lo >= hi returns at once.

Two values are the smallest real case. With the last value as the pivot, two values in the wrong order are fixed by the final swap, and the recursion ends. With two values in the right order, the partition leaves them in place.

A descending array is the mirror of the sorted case. With the last value as pivot, it has the same O(n squared) problem, because the pivot is always the smallest value. Median of three handles it, because the first, middle and last values of a descending run give the middle value as the median.

An array of all equal values is the duplicate case discussed earlier. Lomuto makes about n squared over 2 comparisons, and the three-way partition makes about n.

An array with one very large value at the front of an otherwise sorted run can also cause trouble with the last-value pivot. The pivot choice is the defence. The middle value and random choices make it unlikely that a single unusual value decides every split.

Why the smaller side goes first

When a recursive sort always recurses into the smaller part first, and handles the bigger part with a loop, the call stack can never be deeper than log n. The reason is simple. A smaller part has at most half of the values in its parent range. So each nested recursive call halves the size of the range it works on, and the depth is at most log n.

Many production sorts use this trick, because it makes the stack small even when the pivot choices are poor. It does not make the sort faster. It only protects against running out of stack space on large inputs, which can happen when the worst case is hit.

Interview questions on quick sort

Common questions include these. Why is quick sort O(n log n) on average? What causes the worst case, and how do you avoid it? Is quick sort stable, and can you make it stable? How does quickselect differ from quick sort, and why is its average time linear? How would you handle many duplicates?

A strong answer names the pivot choice, the three-way partition, and the trade-off with merge sort. Quick sort uses little extra memory and is often fast in practice, because its partitions work on neighbouring memory. Merge sort gives a guaranteed time bound and stability, but it needs an extra array.

A full trace on four values

Sort 3 6 1 5 with the Lomuto partition and the last value as the pivot. Each row is one partition.

After the first partition, the pivot 5 sits at index 2. The left range 3 1 and the right range 6 are then sorted by recursion. The left range partitions into 1 3, with the pivot 1 at index 0. The right range has one value. The final array is 1 3 5 6.

Trace the first row carefully, because it shows the whole mechanism. The scan visits 3, 6 and 1. The index i starts at 0. The value 3 is smaller than 5, so swap(a[0], a[0]) runs and i becomes 1. The value 6 is not smaller, so nothing happens. The value 1 is smaller, so swap(a[1], a[2]) moves it to slot 1, and i becomes 2. The last step swaps the pivot 5 into slot 2, which is where i points.

Why the partition places the pivot

The loop keeps a simple invariant. Every value at an index before i is smaller than the pivot. Every value from i up to j - 1 is bigger than or equal to the pivot. When the loop ends, i marks the first index that is not in the smaller group, and the values from lo to i - 1 are all smaller than the pivot.

The final swap moves the pivot into slot i, which is exactly the boundary. The value that was in slot i moves to the end, and it is bigger than or equal to the pivot, so it belongs on the right. That leaves the pivot bigger than everything to its left and not bigger than anything to its right. Its place is final, and the recursion never has to move it again.

Choosing a pivot strategy in practice

Each pivot rule has a cost and a failure case. The last value is free, but it fails on sorted input. Median of three costs a few extra comparisons, and it fixes sorted and reversed input, although a clever adversary can still build a bad case. A random pivot costs one random number per partition, and it makes bad cases unlikely for every input, at the price of a run time that varies a little from run to run.

Many libraries combine these ideas. They use median of three, switch to a different sort when the recursion gets too deep, and use insertion sort for small ranges. In an interview, name the trade-off and say which failure each rule protects against. That answer shows more understanding than naming a single "best" pivot.

Practice

Work on paper first. Then check your code.

1. Change one comparison in the Lomuto partition so that the array is sorted in descending order. Which comparison changes, and what is the new order of the result for 10 7 8 9 1 5?

2. Partition 3 8 2 5 1 4 7 6 with Lomuto, using the last value as the pivot. Write the array after each swap, and give the final array and the pivot index.

3. Explain, using the array 2a 2b 1, why quick sort is not stable. The letters show the original order of the two items with key 2.

4. Use quickselect to find the 2nd largest value in 7 10 4 3 20 15. Hint: the k-th largest is the value at 0-based index n - k, when the array is sorted.

5. Write a random-pivot quick sort. Test it on 5 1 9 3 7 2 8 6 and check that the output is sorted.

6. Sort an array that holds only the values 0, 1 and 2 in one pass, so that all 0s come first, then 1s, then 2s. Use three indexes.

void sortColors(vector<int>& a) {
    int lo = 0, mid = 0, hi = (int)a.size() - 1;
    while (mid <= hi) {
        if (a[mid] == 0) swap(a[lo++], a[mid++]);
        else if (a[mid] == 2) swap(a[mid], a[hi--]);
        else mid++;
    }
}

7. An array of 1000 equal values is sorted with the Lomuto partition and the last value as the pivot. Count the comparisons, and explain how a three-way partition changes the count.

8. Find the k points closest to the origin from a list of (x, y) points, using quickselect on the squared distance. Hint: after the partition, the first k positions should hold the k smallest distances, and the rest of the search goes to only one side.

long long dist2(const pair<int, int>& q) {
    return (long long)q.first * q.first + (long long)q.second * q.second;
}
 
void keepClosest(vector<pair<int, int>>& p, int lo, int hi, int k) {
    if (lo >= hi) return;
    int pivotIdx = lo + (hi - lo) / 2;
    long long pd = dist2(p[pivotIdx]);
    swap(p[pivotIdx], p[hi]);
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (dist2(p[j]) < pd) swap(p[i++], p[j]);
    }
    swap(p[i], p[hi]);
    if (i + 1 == k) return;
    if (i + 1 < k) keepClosest(p, i + 1, hi, k);
    else keepClosest(p, lo, i - 1, k);
}

9. Write an iterative quick sort that uses an explicit stack of ranges instead of recursion. Explain why this protects against a very deep call stack.

void quickSortIter(vector<int>& a) {
    if (a.empty()) return;
    vector<pair<int, int>> st;
    st.push_back({0, (int)a.size() - 1});
    while (!st.empty()) {
        auto [lo, hi] = st.back();
        st.pop_back();
        if (lo >= hi) continue;
        int p = partition(a, lo, hi);
        st.push_back({lo, p - 1});
        st.push_back({p + 1, hi});
    }
}

What you now know

• Quick sort partitions around a pivot and puts the pivot in its final place.
• The Lomuto partition scans with one index and swaps smaller values to the front.
• Quick sort is O(n log n) when splits are balanced, and O(n squared) in the worst case.
• Median of three and random pivots protect against sorted and structured inputs.
• Quickselect recurses into one side only, so it finds the k-th smallest in O(n) on average.
• Many equal values need a three-way partition, or the sort slows to O(n squared).
• Quick sort is not stable, because partition swaps can reverse equal items.