Sorting Algorithms: Quick Sort — Practical Deep Dive

Quick sort is one of the most interesting and widely used sorting algorithms. It is based on a divide-and-conquer approach, and a well-implemented version is fast, practical, and memory-efficient for array-based data.

This guide walks through the algorithm visually, turns the idea into recursive and iterative code, and explains the performance details that matter in practice.

This article was originally published on Medium on 14 May 2022 and has been revised for DeftMove.

What is quick sort?

Quick sort is a comparison-based sorting algorithm. It chooses one value as a pivot, partitions the remaining values around that pivot, and then applies the same process to the two resulting ranges.

Every partitioning scheme creates two ranges around a chosen pivot value, but its exact contract depends on the scheme. The first-pivot and Lomuto versions in this guide place the pivot at a final sorted index:

values less than or equal to the pivot | pivot | values greater than the pivot

They then handle the ranges on the pivot’s left and right independently. The midpoint Hoare-style versions shown later work slightly differently: they return a boundary between two ranges and do not promise that the chosen pivot value finishes at that boundary. In either case, quick sort keeps dividing the remaining work until every range contains zero or one value.

Efficient array implementations rearrange values within the original array instead of allocating a new array at every step. Quick sort is therefore conventionally described as in place, although a recursive implementation still consumes call-stack space.

How does it work?

The complete algorithm has four main steps:

1. Choose an element to use as the pivot.
2. Partition the range by moving smaller values to the pivot’s left and larger values to its right.
3. Apply quick sort to the left range.
4. Apply quick sort to the right range.

The pivot can be the first value, the last value, a middle value, or a value selected by a more deliberate strategy. The choice does not change the basic algorithm, but it can have a major effect on performance.

A detailed partition example

Start with this array:

[8, 5, 2, 9, 5, 6, 3]

For this walkthrough, choose the first value, 8, as the pivot. Begin with a left pointer at 5 and a right pointer at 3.

• Move the left pointer while its value belongs on the pivot’s left.
• Move the right pointer while its value belongs on the pivot’s right.
• When both pointers stop, swap the misplaced values.
• When the pointers cross, swap the pivot with the value at the right pointer.

In the first partition, the left pointer stops at 9 and the right pointer stops at 3. Swapping them moves both values to the correct side of 8. The scan continues until the pointers cross, then 8 is placed in its final position.

That produces a one-value range containing 9 and the remaining range [6, 5, 2, 3, 5]. A range with only one value is already sorted.

Now repeat the process on [6, 5, 2, 3, 5]. Choose 6 as the next pivot. Every remaining value is smaller, so the pointers eventually cross and 6 swaps into its final position.

The same rule keeps reducing the unsorted ranges. The fourth iteration partitions [5, 5, 2, 3] around the first 5, producing [3, 5, 2, 5]. The fifth partitions [3, 5, 2] around 3 and produces [2, 3, 5]. The last two recursive calls each contain one value, so no more swaps are required.

C# implementations

The first version mirrors the visual example: it selects the first value as the pivot and moves two pointers inward. The other two versions isolate a midpoint-pivot partition function, then manage the remaining ranges recursively or with an explicit stack.

using System;

public static class FirstPivotQuickSort
{
    public static void Sort(int[] values)
    {
        ArgumentNullException.ThrowIfNull(values);
        SortRange(values, 0, values.Length - 1);
    }

    private static void SortRange(int[] values, int low, int high)
    {
        if (low >= high)
            return;

        int pivotIndex = low;
        int left = low + 1;
        int right = high;

        while (left <= right)
        {
            while (left <= right && values[left] <= values[pivotIndex])
                left++;

            while (left <= right && values[right] >= values[pivotIndex])
                right--;

            if (left < right)
                Swap(values, left, right);
        }

        Swap(values, pivotIndex, right);

        SortRange(values, low, right - 1);
        SortRange(values, right + 1, high);
    }

    private static void Swap(int[] values, int first, int second) =>
        (values[first], values[second]) =
            (values[second], values[first]);
}

using System;

public static class RecursiveQuickSort
{
    public static void Sort(int[] values)
    {
        ArgumentNullException.ThrowIfNull(values);
        SortRange(values, 0, values.Length - 1);
    }

    private static void SortRange(int[] values, int low, int high)
    {
        if (low >= high)
            return;

        int split = Partition(values, low, high);
        SortRange(values, low, split - 1);
        SortRange(values, split, high);
    }

    private static int Partition(int[] values, int left, int right)
    {
        int pivot = values[left + (right - left) / 2];

        while (left <= right)
        {
            while (values[left] < pivot)
                left++;

            while (values[right] > pivot)
                right--;

            if (left <= right)
            {
                (values[left], values[right]) =
                    (values[right], values[left]);
                left++;
                right--;
            }
        }

        return left;
    }
}

using System;
using System.Collections.Generic;

public static class IterativeQuickSort
{
    public static void Sort(int[] values)
    {
        ArgumentNullException.ThrowIfNull(values);

        if (values.Length < 2)
            return;

        var ranges = new Stack<(int Low, int High)>();
        ranges.Push((0, values.Length - 1));

        while (ranges.Count > 0)
        {
            var (low, high) = ranges.Pop();
            int split = Partition(values, low, high);

            if (low < split - 1)
                ranges.Push((low, split - 1));

            if (split < high)
                ranges.Push((split, high));
        }
    }

    private static int Partition(int[] values, int left, int right)
    {
        int pivot = values[left + (right - left) / 2];

        while (left <= right)
        {
            while (values[left] < pivot)
                left++;

            while (values[right] > pivot)
                right--;

            if (left <= right)
            {
                (values[left], values[right]) =
                    (values[right], values[left]);
                left++;
                right--;
            }
        }

        return left;
    }
}

First-pivot version

The first-pivot version is useful for understanding the pointer movement shown in the diagrams. After the pointers cross, it swaps the pivot with the right pointer and recursively sorts the two ranges around it.

Its weakness is predictability. If the input is already sorted or reverse-sorted, the first value is consistently an extreme value and the partitions become badly unbalanced.

Recursive midpoint version

The recursive version separates the algorithm into two responsibilities:

• Partition moves the left and right pointers toward each other and swaps misplaced values.
• SortRange recursively processes the two ranges returned by the partition.

Choosing the midpoint index protects this particular implementation from the obvious already-sorted-input problem. It does not guarantee balanced partitions for every arrangement of values.

Iterative version

The iterative version replaces recursive calls with an explicit Stack. Each stack item represents a range that still needs to be sorted. The underlying partition work is the same; only the way pending ranges are managed changes.

Neither form is universally faster. The explicit-stack version gives direct control over pending work and avoids recursive call depth, while the recursive form is usually shorter and easier to follow. Both can require O(n) stack space if partitions remain badly unbalanced.

The same algorithm in C#, Python, and Go

The following versions use Lomuto partitioning instead. They choose the last value as the pivot, maintain a boundary for smaller values, and finally move the pivot into that boundary.

using System;

public static class QuickSort
{
    public static void Sort(int[] values)
    {
        ArgumentNullException.ThrowIfNull(values);
        SortRange(values, 0, values.Length - 1);
    }

    private static void SortRange(int[] values, int low, int high)
    {
        if (low >= high)
            return;

        int pivotIndex = Partition(values, low, high);
        SortRange(values, low, pivotIndex - 1);
        SortRange(values, pivotIndex + 1, high);
    }

    private static int Partition(int[] values, int low, int high)
    {
        int pivot = values[high];
        int store = low;

        for (int scan = low; scan < high; scan++)
        {
            if (values[scan] <= pivot)
            {
                (values[store], values[scan]) =
                    (values[scan], values[store]);
                store++;
            }
        }

        (values[store], values[high]) =
            (values[high], values[store]);

        return store;
    }
}

def quick_sort(values: list[int]) -> None:
    def partition(low: int, high: int) -> int:
        pivot = values[high]
        store = low

        for scan in range(low, high):
            if values[scan] <= pivot:
                values[store], values[scan] = values[scan], values[store]
                store += 1

        values[store], values[high] = values[high], values[store]
        return store

    def sort_range(low: int, high: int) -> None:
        if low >= high:
            return

        pivot_index = partition(low, high)
        sort_range(low, pivot_index - 1)
        sort_range(pivot_index + 1, high)

    sort_range(0, len(values) - 1)

func QuickSort(values []int) {
	quickSortRange(values, 0, len(values)-1)
}

func quickSortRange(values []int, low, high int) {
	if low >= high {
		return
	}

	pivotIndex := partition(values, low, high)
	quickSortRange(values, low, pivotIndex-1)
	quickSortRange(values, pivotIndex+1, high)
}

func partition(values []int, low, high int) int {
	pivot := values[high]
	store := low

	for scan := low; scan < high; scan++ {
		if values[scan] <= pivot {
			values[store], values[scan] = values[scan], values[store]
			store++
		}
	}

	values[store], values[high] = values[high], values[store]
	return store
}

All three implementations mutate the supplied array or slice and handle empty collections, one-value collections, duplicate values, and negative integers. Seeing the same invariant in several languages helps separate the algorithm from the syntax used to express it.

Time complexity

Partitioning a range of n values requires linear work: each value is inspected a constant number of times. The total running time depends on how evenly those partitions divide the remaining work.

Worst case: repeatedly choosing an extreme value

Consider a sorted array such as [10, 20, 30, 40, 50] when the first value is always the pivot. The first partition leaves one empty range and another with four values. The next leaves a range of three, then two, then one.

The work is proportional to:

(n - 1) + (n - 2) + ... + 2 + 1

That sum grows quadratically, giving O(n²) time.

Best case: balanced partitions

When each pivot splits its range close to the middle, the recursion tree has about log n levels. Across any one level, partitioning still examines a total of roughly n values, so the total is O(n log n).

A randomized pivot makes consistently bad partitions unlikely and gives expected O(n log n) performance. It does not remove the theoretical O(n²) worst case.

Space complexity

The partition operation itself uses O(1) extra storage because it rearranges values in place. A recursive implementation uses additional call-stack space:

• Average recursive depth: O(log n) when partitions stay reasonably balanced.
• Worst recursive depth: O(n) when every partition removes only one value.

The iterative version uses its explicit stack instead. Its size depends on the order in which it processes and defers the two partitions: it is commonly O(log n), but an adversarial sequence can accumulate O(n) pending ranges. An implementation can guarantee a logarithmic bound by always processing the smaller partition immediately and deferring the larger one.

Practical improvements

Real implementations often add safeguards around the elegant core algorithm:

• Randomized pivot: makes adversarial or consistently poor splits less likely.
• Median of three: estimates a useful pivot from the first, middle, and last values.
• Three-way partitioning: groups values smaller than, equal to, and greater than the pivot; this is especially useful when duplicates are common.
• Insertion sort for tiny ranges: avoids recursive overhead where a simple loop is faster.
• Introsort fallback: switches to heap sort if the recursion becomes too deep, preserving an O(n log n) worst-case bound.
• Smaller-range recursion: limits call-stack growth by recursing into the smaller side first.

The best combination depends on the data, language runtime, and standard library. A classroom implementation should make the invariant clear; a production implementation also needs to defend against troublesome input shapes.

Frequently asked questions

Is quick sort stable?

Typical in-place quick sort is not stable. Swaps can change the relative order of records that have equal keys. Use a stable algorithm when preserving that earlier order is a requirement.

Is quick sort adaptive?

The basic algorithm is not adaptive: it does not automatically benefit from values that are already in order. With a poor pivot rule, sorted data can even create its worst case. Hybrid implementations can add checks and strategies that behave better on common input patterns.

Is quick sort in place?

For arrays, it is conventionally considered in place because partitioning needs only constant auxiliary storage and does not create another array proportional to the input. The recursive call stack is still real: it uses O(log n) space on average and O(n) in the worst case.

Is quick sort suitable for linked lists?

It can be implemented for linked lists, but merge sort is usually a more natural fit. Linked lists do not provide constant-time random indexing, while merge sort can split and merge nodes without the array-style swaps that make quick sort attractive.

Is quick sort better than merge sort?

Neither algorithm wins in every situation.

• Quick sort is often an excellent choice for arrays because it has good cache behaviour and needs little auxiliary storage.
• Merge sort guarantees O(n log n) time, is naturally stable, and works particularly well with linked lists and sequential data.
• A straightforward array merge sort needs an O(n) auxiliary buffer, whereas quick sort’s partitioning is in place.

Choose according to the guarantees the application needs, not only the average running time.

Why use quick sort when its worst case is O(n²)?

Its constant factors are good, its memory access is friendly to modern hardware, and sensible pivot strategies make the worst case uncommon in ordinary data. When a hard worst-case guarantee is required, use a guarded hybrid such as introsort or select another algorithm.

How does quick sort differ from selection sort?

Selection sort chooses an output position and searches for the value that belongs there. Quick sort chooses a pivot value and partitions the input to discover where that pivot belongs. Selection sort always takes O(n²) comparisons; quick sort averages O(n log n).

When should I use it?

Quick sort is a strong option for in-memory arrays when average performance and low auxiliary storage matter. Avoid a basic implementation when stable ordering is required, inputs can deliberately trigger poor pivots, or recursion depth cannot be controlled.

Conclusion

Quick sort turns one compact invariant into a complete sorting algorithm: choose a pivot, partition the values around it, and repeat on the remaining ranges. Once partitioning is clear, both the recursive and iterative implementations follow naturally.

The practical lesson is to look beyond the average O(n log n) headline. Pivot choice, duplicate handling, and stack depth decide whether quick sort remains fast and safe for the data you actually need to sort.