ZetCode

C# Quick Sort

last modified November 6, 2026

In this article we implement the quicksort algorithm in C#. We trace how the array is partitioned, show why the choice of the pivot matters, and build an optimized version that we compare with Array.Sort.

Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.

Quicksort algorithm

Quicksort, developed by Tony Hoare in 1959, is a divide and conquer algorithm. It selects one element as the pivot and partitions the array: smaller elements are moved before the pivot, the other elements after it. The pivot is then in its final position, and the two parts are sorted recursively.

PropertyValue
Best and average caseO(n log n)
Worst caseO(n²), when the pivot is always the smallest or largest element
Extra memoryO(log n) for the recursion, if done carefully
Stableno

In practice, quicksort is one of the fastest sorting algorithms. The Array.Sort method uses introsort, a quicksort that switches to heap sort when the recursion gets too deep and to insertion sort for small partitions.

C# quicksort example

The first example uses the Lomuto partition scheme with the last element as the pivot.

Program.cs 
int[] nums = [10, 80, 30, 90, 40, 50, 70];

QuickSort(nums, 0, nums.Length - 1);
Console.WriteLine(string.Join(" ", nums));

static void QuickSort(int[] arr, int lo, int hi)
{
    if (lo >= hi) return;

    int p = Partition(arr, lo, hi);
    QuickSort(arr, lo, p - 1);
    QuickSort(arr, p + 1, hi);
}

static int Partition(int[] arr, int lo, int hi)
{
    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);
    return i;
}

The method sorts the range from lo to hi in place. 

int p = Partition(arr, lo, hi);
QuickSort(arr, lo, p - 1);
QuickSort(arr, p + 1, hi);

The Partition method returns the final position of the pivot. The elements before and after it are sorted recursively. 

int pivot = arr[hi];
int i = lo;

for (int j = lo; j < hi; j++)
{
    if (arr[j] < pivot)
    {
        (arr[i], arr[j]) = (arr[j], arr[i]);
        i++;
    }
}

The elements before index i are smaller than the pivot. Each smaller element found by the loop is swapped to position i, and the boundary moves to the right. 

(arr[i], arr[hi]) = (arr[hi], arr[i]);
return i;

Finally, the pivot is swapped into the boundary position. 

$ dotnet run
10 30 40 50 70 80 90

Partitions step by step

The next example prints each pivot with the two parts around it after the partitioning.

Program.cs 
int[] nums = [7, 2, 9, 4, 3, 8, 6];

QuickSort(nums, 0, nums.Length - 1);
Console.WriteLine($"sorted: {string.Join(" ", nums)}");

static void QuickSort(int[] arr, int lo, int hi)
{
    if (lo >= hi) return;

    int p = Partition(arr, lo, hi);

    string left = string.Join(" ", arr[lo..p]);
    string right = string.Join(" ", arr[(p + 1)..(hi + 1)]);
    Console.WriteLine($"pivot {arr[p]}: [{left}] {arr[p]} [{right}]");

    QuickSort(arr, lo, p - 1);
    QuickSort(arr, p + 1, hi);
}

static int Partition(int[] arr, int lo, int hi)
{
    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);
    return i;
}

The first pivot is 6, the last element. After the partitioning, the smaller elements 2, 4, and 3 are on its left and the larger ones on its right. The pivot 7 is the smallest element of its part, so the left part is empty. 

$ dotnet run
pivot 6: [2 4 3] 6 [9 8 7]
pivot 3: [2] 3 [4]
pivot 7: [] 7 [8 9]
pivot 9: [8] 9 []
sorted: 2 3 4 6 7 8 9

Generic quicksort with random pivot

The generic version takes an IComparer<T> and picks a random pivot.

Program.cs 
string[] langs = ["Rust", "Go", "C#", "Python", "Java", "Zig", "Kotlin"];

QuickSort(langs, StringComparer.Ordinal);
Console.WriteLine(string.Join(" ", langs));

QuickSort(langs, Comparer<string>.Create((a, b) => string.CompareOrdinal(b, a)));
Console.WriteLine(string.Join(" ", langs));

static void QuickSort<T>(T[] arr, IComparer<T> comparer)
{
    Sort(0, arr.Length - 1);

    void Sort(int lo, int hi)
    {
        if (lo >= hi) return;

        int pivotIndex = Random.Shared.Next(lo, hi + 1);
        (arr[pivotIndex], arr[hi]) = (arr[hi], arr[pivotIndex]);

        T pivot = arr[hi];
        int i = lo;

        for (int j = lo; j < hi; j++)
        {
            if (comparer.Compare(arr[j], pivot) < 0)
            {
                (arr[i], arr[j]) = (arr[j], arr[i]);
                i++;
            }
        }

        (arr[i], arr[hi]) = (arr[hi], arr[i]);

        Sort(lo, i - 1);
        Sort(i + 1, hi);
    }
}

The recursive part is a local function that captures the array and the comparer. 

int pivotIndex = Random.Shared.Next(lo, hi + 1);
(arr[pivotIndex], arr[hi]) = (arr[hi], arr[pivotIndex]);

A random element is swapped to the end and used as the pivot. The upper bound of Next is exclusive, hence hi + 1. 

QuickSort(langs, Comparer<string>.Create((a, b) => string.CompareOrdinal(b, a)));

A comparer with reversed arguments sorts the names in descending order. 

$ dotnet run
C# Go Java Kotlin Python Rust Zig
Zig Rust Python Kotlin Java Go C#

The choice of the pivot

If the pivot is always the smallest or the largest element, one of the parts is empty and the other has only one element less. This happens when we take the last element as the pivot and the array is already sorted. The following example counts comparisons and the recursion depth for 5,000 elements.

Program.cs 
const int N = 5_000;
int[] sorted = [.. Enumerable.Range(0, N)];
int[] random = [.. Enumerable.Range(0, N).Select(_ => Random.Shared.Next(N))];

Run("last element pivot, random", random, randomPivot: false);
Run("last element pivot, sorted", sorted, randomPivot: false);
Run("random pivot, sorted", sorted, randomPivot: true);

static void Run(string label, int[] data, bool randomPivot)
{
    var stats = new Stats();
    QuickSort([.. data], 0, data.Length - 1, 1, randomPivot, stats);
    Console.WriteLine($"{label,-28} {stats.Comparisons,11:N0} comparisons, depth {stats.MaxDepth}");
}

static void QuickSort(int[] arr, int lo, int hi, int depth, bool randomPivot, Stats stats)
{
    if (lo >= hi) return;

    stats.MaxDepth = Math.Max(stats.MaxDepth, depth);

    if (randomPivot)
    {
        int r = Random.Shared.Next(lo, hi + 1);
        (arr[r], arr[hi]) = (arr[hi], arr[r]);
    }

    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        stats.Comparisons++;

        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);

    QuickSort(arr, lo, i - 1, depth + 1, randomPivot, stats);
    QuickSort(arr, i + 1, hi, depth + 1, randomPivot, stats);
}

class Stats
{
    public long Comparisons { get; set; }
    public int MaxDepth { get; set; }
}

A Stats object collects the counts across the recursive calls. 

QuickSort([.. data], 0, data.Length - 1, 1, randomPivot, stats);

Each run sorts a copy of the data, created by a collection expression with the spread element.

With the last element as the pivot, sorted input needs about n²/2 comparisons and the recursion depth is n - 1. For larger arrays, such recursion can overflow the stack. A random pivot makes this worst case very unlikely, whatever the input order. The results for random data vary slightly between runs. 

$ dotnet run
last element pivot, random        68,001 comparisons, depth 26
last element pivot, sorted    12,497,500 comparisons, depth 4999
random pivot, sorted              68,259 comparisons, depth 27

Optimized quicksort vs Array.Sort

The last example adds three common optimizations and sorts a million random integers.

Program.cs 
#:property PublishAot=false

using System.Diagnostics;

var rnd = new Random(17);
int[] data = [.. Enumerable.Range(0, 1_000_000).Select(_ => rnd.Next())];

int[] a = [.. data];
var sw = Stopwatch.StartNew();
QuickSort(a, 0, a.Length - 1);
Console.WriteLine($"Quick sort: {sw.ElapsedMilliseconds} ms");

int[] b = [.. data];
sw.Restart();
Array.Sort(b);
Console.WriteLine($"Array.Sort: {sw.ElapsedMilliseconds} ms");

Console.WriteLine($"Same result: {a.SequenceEqual(b)}");

static void QuickSort(int[] arr, int lo, int hi)
{
    while (lo < hi)
    {
        if (hi - lo < 16)
        {
            InsertionSort(arr, lo, hi);
            return;
        }

        int p = Partition(arr, lo, hi);

        if (p - lo < hi - p)
        {
            QuickSort(arr, lo, p - 1);
            lo = p + 1;
        }
        else
        {
            QuickSort(arr, p + 1, hi);
            hi = p - 1;
        }
    }
}

static int Partition(int[] arr, int lo, int hi)
{
    int mid = lo + (hi - lo) / 2;

    if (arr[mid] < arr[lo]) (arr[mid], arr[lo]) = (arr[lo], arr[mid]);
    if (arr[hi] < arr[lo]) (arr[hi], arr[lo]) = (arr[lo], arr[hi]);
    if (arr[hi] < arr[mid]) (arr[hi], arr[mid]) = (arr[mid], arr[hi]);

    (arr[mid], arr[hi]) = (arr[hi], arr[mid]);
    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);
    return i;
}

static void InsertionSort(int[] arr, int lo, int hi)
{
    for (int i = lo + 1; i <= hi; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= lo && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

The optimizations improve the pivot, handle small partitions, and limit the recursion depth. 

if (arr[mid] < arr[lo]) (arr[mid], arr[lo]) = (arr[lo], arr[mid]);
if (arr[hi] < arr[lo]) (arr[hi], arr[lo]) = (arr[lo], arr[hi]);
if (arr[hi] < arr[mid]) (arr[hi], arr[mid]) = (arr[mid], arr[hi]);

The median of three sorts the first, middle, and last element; the middle value becomes the pivot. It works well for sorted and reversed data. 

if (hi - lo < 16)
{
    InsertionSort(arr, lo, hi);
    return;
}

For small partitions, insertion sort is faster than further recursion. 

if (p - lo < hi - p)
{
    QuickSort(arr, lo, p - 1);
    lo = p + 1;
}

Only the smaller part is sorted by a recursive call; the larger part is handled by the next iteration of the loop. Each recursive call gets at most half of the elements, so the depth is at most log₂ n. 

#:property PublishAot=false

File-based apps are published with Native AOT by default. The directive turns this off, so the release build does not pull in the AOT compiler package.

We run the program in the Release configuration. The built-in method is still more than twice as fast; it is heavily tuned, for instance it works with references instead of array indexes to avoid bounds checks. 

$ dotnet run -c Release benchmark.cs
Quick sort: 159 ms
Array.Sort: 64 ms
Same result: True

Source

Array.Sort method

In this article we have implemented the quicksort algorithm in C#.

Other sorting algorithms in C#:

Author

My name is Jan Bodnar and I am a passionate programmer with many years of programming experience. I have been writing programming articles since 2007.

So far, I have written over 1400 articles and 8 e-books. I have over eight years of experience in teaching programming.

List all C# tutorials.