Quick Sort Algorithm: Complete Guide with Rust and Go

Quick sort is a divide-and-conquer algorithm that rearranges values around a pivot before making recursive calls.

After partitioning, the range has three logical regions:

values < pivot | values == pivot | values > pivot

The equal region is already in its final relative value position. Quick sort recursively processes only the smaller and larger regions.

Unlike merge sort, quick sort does not need an O(n) merge buffer. Its partitioning is in place and often has good array locality. The trade-off is that its performance depends on pivot quality: expected time is O(n log n), but the worst case is O(n²).

How Quick Sort Works

For a range [start, end):

1. Return if it contains fewer than two elements.
2. Choose a pivot value.
3. Partition values into less-than, equal-to, and greater-than regions.
4. Recursively sort the less-than region.
5. Recursively sort the greater-than region.

quick_sort(array, start, end):
    if end - start <= 1:
        return

    pivot = choose_pivot(array, start, end)
    (equal_start, equal_end) = partition_three_way(array, pivot)

    quick_sort(array, start, equal_start)
    quick_sort(array, equal_end, end)

The implementation below chooses the middle array position as an understandable deterministic baseline and uses three-way partitioning. For adversarial or unknown input, randomize the pivot or shuffle the array first.

Three-Way Partitioning

Maintain three boundaries:

[start, less)  < pivot
[less, scan)   == pivot
[scan, greater) unknown
[greater, end) > pivot

Inspect array[scan]:

• If it is smaller, swap it with array[less], then advance both boundaries.
• If it is equal, advance scan.
• If it is greater, decrement greater and swap with that position. Do not advance scan because the incoming value has not been classified.

When scan == greater, no unknown values remain.

Quick Sort Dry Run

Partition:

[4, 6, 2, 5, 7, 9, 1, 3]

Choose the middle-position value 5 as the pivot. Three-way partitioning produces:

[4, 3, 2, 1] | [5] | [9, 7, 6]
 values < 5    equal   values > 5

The exact order inside the left and right regions does not matter yet. Their only required property is their relationship to the pivot.

Recursively sort both sides:

quick_sort([4, 3, 2, 1]) -> [1, 2, 3, 4]
quick_sort([9, 7, 6])    -> [6, 7, 9]

The complete result is:

[1, 2, 3, 4, 5, 6, 7, 9]

Nothing merges afterward. Partitioning placed the pivot region between two independent subproblems before recursion.

Why Quick Sort Is Correct

The partition loop maintains four regions: values smaller than the pivot, values equal to it, unclassified values, and values greater than it. Every iteration classifies at least one value, so the unknown region eventually becomes empty.

After partitioning:

• Every value in the left subrange is less than the pivot.
• Every value in the middle is equal to the pivot.
• Every value in the right subrange is greater than the pivot.

Assume recursively that quick sort correctly sorts smaller ranges. Sorting the left and right subranges cannot move a value across the equal pivot region. Their concatenation is therefore sorted.

Cornell's sorting notes similarly define partitioning as linear work that fixes the pivot region and leaves independent recursive sorting problems.

Quick Sort in Rust

pub fn quick_sort<T: Ord + Clone>(values: &mut [T]) {
    let len = values.len();
    sort_range(values, 0, len);
}

fn sort_range<T: Ord + Clone>(values: &mut [T], start: usize, end: usize) {
    if end - start <= 1 {
        return;
    }

    let pivot = values[start + (end - start) / 2].clone();
    let (equal_start, equal_end) = partition(values, start, end, &pivot);

    sort_range(values, start, equal_start);
    sort_range(values, equal_end, end);
}

fn partition<T: Ord>(
    values: &mut [T],
    start: usize,
    end: usize,
    pivot: &T,
) -> (usize, usize) {
    let mut less = start;
    let mut scan = start;
    let mut greater = end;

    while scan < greater {
        if values[scan] < *pivot {
            values.swap(less, scan);
            less += 1;
            scan += 1;
        } else if values[scan] > *pivot {
            greater -= 1;
            values.swap(scan, greater);
        } else {
            scan += 1;
        }
    }

    (less, greater)
}

#[cfg(test)]
mod tests {
    use super::quick_sort;

    #[test]
    fn sorts_values_and_duplicates() {
        let mut values = [4, 6, 2, 5, 7, 9, 1, 3];
        quick_sort(&mut values);
        assert_eq!(values, [1, 2, 3, 4, 5, 6, 7, 9]);

        let mut duplicates = [3, 1, 3, 2, 1, 3];
        quick_sort(&mut duplicates);
        assert_eq!(duplicates, [1, 1, 2, 3, 3, 3]);
    }
}

Cloning the pivot is necessary because partition swaps can move the element originally occupying the pivot index.

Quick Sort in Go

package main

import "fmt"

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 | ~string
}

func QuickSort[T Ordered](values []T) {
	sortRange(values, 0, len(values))
}

func sortRange[T Ordered](values []T, start, end int) {
	if end-start <= 1 {
		return
	}

	pivot := values[start+(end-start)/2]
	equalStart, equalEnd := partition(values, start, end, pivot)

	sortRange(values, start, equalStart)
	sortRange(values, equalEnd, end)
}

func partition[T Ordered](values []T, start, end int, pivot T) (int, int) {
	less, scan, greater := start, start, end

	for scan < greater {
		if values[scan] < pivot {
			values[less], values[scan] = values[scan], values[less]
			less++
			scan++
		} else if values[scan] > pivot {
			greater--
			values[scan], values[greater] = values[greater], values[scan]
		} else {
			scan++
		}
	}

	return less, greater
}

func main() {
	numbers := []int{4, 6, 2, 5, 7, 9, 1, 3}
	QuickSort(numbers)
	fmt.Println(numbers)
}

Use the standard sorting facilities for production code. Go's slices.Sort and Rust's slice::sort_unstable provide tested general-purpose unstable sorting.

Complexity Analysis

Partitioning a range of n values takes O(n). Total time depends on the resulting split.

Balanced recurrence:

T(n) = 2T(n / 2) + O(n) = O(n log n)

Worst-case recurrence:

T(n) = T(n - 1) + O(n) = O(n²)

Princeton's quicksort documentation describes randomized input as protection against quadratic patterns and recommends three-way partitioning for duplicate-heavy keys.

Pivot Selection Strategies

First or last element

Simple, but sorted and reverse-sorted inputs can repeatedly create one-sided partitions.

Middle position

Avoids the most obvious sorted-input failure for some patterns, but remains deterministic and can still be defeated. The tutorial implementation uses it for reproducibility.

Random pivot

Choose a uniformly random position within each range, or shuffle once before sorting. This makes the expected complexity O(n log n) independent of the original input order.

Median of three

Use the median of the first, middle, and last values. It is a useful heuristic but not a worst-case guarantee.

Two-Way vs Three-Way Partitioning

Two-way partitioning creates values below the pivot on one side and values above or equal on the other. With many duplicates, equal values can repeatedly enter recursive calls.

Three-way partitioning creates:

< pivot | == pivot | > pivot

The equal region is excluded from recursion. If every value is equal, one partition pass finishes the complete sort in O(n) time.

Is Quick Sort Stable?

Standard in-place quick sort is not stable. Long-distance partition swaps can move equal-key records across one another.

Stability is usually not added to in-place quick sort because preserving relative order requires extra bookkeeping, additional storage, or a more complicated stable partition. When stable ordering is required, merge sort or the language's stable standard sorter is normally clearer.

Controlling Recursion Depth

Even randomized quick sort has a theoretical O(n) stack worst case. A robust implementation can:

1. Recurse on the smaller partition.
2. Continue with the larger partition using a loop.

The smaller recursive side is at most half the current range, limiting simultaneous stack depth to O(log n), regardless of partition quality. Another production strategy is introsort: switch to heap sort when recursion exceeds a depth limit.

Common Quick Sort Mistakes

• Including the equal pivot region in a recursive call, causing non-termination.
• Advancing scan after swapping an unclassified right-side value into it.
• Holding a reference to an array pivot while swaps move that element.
• Claiming guaranteed O(n log n) time; ordinary quick sort has an O(n²) worst case.
• Ignoring O(n) worst-case recursion stack usage.
• Using fixed first/last pivots on presorted input.
• Using two-way partitioning without considering duplicate-heavy data.
• Expecting in-place quick sort to be stable.

Quick Sort vs Merge Sort

Use merge sort when stability or worst-case predictability matters. Quick sort is attractive when in-place array partitioning and practical locality matter, provided pivot and stack-depth risks are handled.

The Bottom Line

Quick sort performs its divide-and-conquer split through partitioning:

choose pivot -> partition -> recursively sort outer regions

Its expected runtime is O(n log n), but repeated poor pivots cause O(n²) time and O(n) stack depth. Randomized pivot selection reduces input-pattern risk, three-way partitioning handles duplicates efficiently, and smaller-side recursion can control stack usage.

Continue through the Sorting Algorithms category for the complete series of Rust and Go tutorials.