Quicksort Algorithm in C#

Updated on November 5, 2026

Quicksort is one of the most efficient algorithms that we can use to accomplish our sorting goals. It picks a pivot, moves smaller elements to its left and larger ones to its right, then sorts both sides the same way. On average, it runs in O(N log N) time.

We are going to implement Quicksort in C#, analyze its time and space complexity, and see what happens when we feed it an array that is already sorted.

Let’s start. 

What Is the Quicksort Algorithm?

Quicksort is a “divide and conquer” sorting algorithm. Just like merge sort, it splits the problem into smaller pieces, but it does the hard work before the split instead of after it.

It chooses one element as the pivot and partitions the array around it. When the partition is done, every element in the left part is less than or equal to the pivot and every element in the right part is greater than or equal to it.

Then the algorithm calls itself on each part. A part with one element is already sorted, so the recursion stops there.

Quicksort sorts the array in place. Apart from a few index variables, the only extra memory it uses is the call stack for the recursion.

On average, it runs in O(N log N) time. When the pivot keeps landing on the smallest or largest value, the partitions become lopsided, and the running time grows to O(N²).

The left subarray contains all elements that are less than the pivot. The right subarray contains all the elements that are greater than the pivot. We recursively repeat this process until we sort the array. We can select the pivot the algorithm uses during this process in different ways:

• The first element of the array
• The last element of the array
• A random element of the array
• Median element of the array

So, what is the best pivot to select when implementing the quicksort algorithm? The answer to this question is not that simple.

Picking the middle element is cheap. Its index is leftIndex + (rightIndex - leftIndex) / 2, one line of arithmetic in every call. Finding the true median of the values is the expensive part, because that means looking at the whole range.

That’s why the median element strategy usually means the median-of-three technique, where we select the pivot based on the median of three values such as the first, middle, and last elements of the array.

The first or last element is the simplest choice and works well on random data. On data that is already sorted, though, it hits the worst case every time. The middle element, a random element and the median of three all make that worst case unlikely on real data.

Let’s take a deep dive and learn how quicksort works.

How Does the Quicksort Algorithm Work?

To illustrate how the quicksort algorithm works, let’s assume we intend to sort this array:

int[] array = { 52, 96, 67, 71, 42, 38, 39, 40, 14 };

In this article, let’s take the first element (52) as the pivot as we learn how to implement quicksort.

First Partition Level

We start with two indexes, i on the left and j on the right, and compare their elements against the pivot value, 52. i moves right until it finds an element that is not less than 52, and j moves left until it finds an element that is not greater than 52. Then we swap the two and keep going.

The pivot itself is not less than 52, so i stops right away on 52, while j stops on 14. We swap them and the array becomes:

14, 96, 67, 71, 42, 38, 39, 40, 52

Mind you, the pivot is a value, not a position. 52 has moved to the end of the array, and that’s fine: we keep comparing against 52.

Next, we can see that 96 is greater than the pivot element while 40 is less than the pivot, so we swap their positions:

14, 40, 67, 71, 42, 38, 39, 96, 52

As we traverse the array, 67 is greater than the pivot while 39 is less than the pivot, so we swap their positions:

14, 40, 39, 71, 42, 38, 67, 96, 52

Then 71 and 38 change places:

14, 40, 39, 38, 42, 71, 67, 96, 52

Now i moves past 42, which is less than the pivot, and stops on 71. j stops on 42. The two indexes have crossed, and that ends the first partition. Everything to the left of 71 is less than 52, and everything from 71 onward is 52 or greater.

Given the fact that quicksort is recursive, in the next iteration, we are going to have two subarrays based on the identified splitting point.

Second Partition Level

The left subarray is 14, 40, 39, 38, 42 and the right subarray is 71, 67, 96, 52.

Our code sorts the left subarray first, but the order doesn’t change the result, so let’s start with the right subarray and take 71 as the pivot. i stops on 71 itself, and j stops on 52, the first element from the right that is not greater than 71. We swap them:

52, 67, 96, 71

After that swap, i stops on 96 and j stops on 67, so the indexes cross between them. This splits the subarray into 52, 67 and 96, 71.

We are going to repeat the same process for the left subarray and select 14 as the pivot for that subarray. 14 is the smallest element, so nothing moves. The split leaves 14 alone on the left and 40, 39, 38, 42 on the right.

Third Partition Level

In the last iteration, quicksort takes the first element of each remaining subarray as its pivot.

In 40, 39, 38, 42, the pivot is 40. 40 and 38 swap their positions:

38, 39, 40, 42

In 96, 71, the pivot is 96, and 96 and 71 swap:

71, 96

52, 67 is already in order, so its partition moves nothing. The same goes for the two pairs left over from the first subarray, 38, 39 and 40, 42, and with that the recursion ends.

We can see that by using the divide and conquer strategy we complete the sorting process efficiently with the result being:

14, 38, 39, 40, 42, 52, 67, 71, 96

Let’s learn how to implement the quicksort algorithm in C#. 

How to Implement Quicksort in C#?

To implement quicksort in C#, we need one recursive method that sorts a range of an int[] in place. It takes the array and the first and last index of the range, and the first call passes 0 and array.Length - 1.

Inside, the method picks the pivot value, here the first element of the range. Two indexes, i and j, start at the two ends and walk toward each other.

i stops on an element that is not less than the pivot, and j stops on one that is not greater than it. If they haven’t crossed yet, we swap the two elements and move both indexes one step.

When the indexes cross, everything up to j belongs on the left and everything from i on belongs on the right. The method then calls itself on each part that still has more than one element.

We are going to define a method SortArray() in a QuickSortMethods class of a new console app as our entry point into the sorting algorithm. The method takes three parameters int[] array, int leftIndex and int rightIndex:

public int[] SortArray(int[] array, int leftIndex, int rightIndex)
{
    var i = leftIndex;
    var j = rightIndex;
    var pivot = array[leftIndex];

    while (i <= j)
    {
        while (array[i] < pivot)
        {
            i++;
        }
        
        while (array[j] > pivot)
        {
            j--;
        }

        if (i <= j)
        {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
    
    if (leftIndex < j)
        SortArray(array, leftIndex, j);

    if (i < rightIndex)
        SortArray(array, i, rightIndex);

    return array;
}

SortArray() starts by assigning the values of the leftIndex and rightIndex to new variables i and j, which we are going to use when iterating through the array. 

Next, we set the pivot as the leftmost element in the array:

var pivot = array[leftIndex];

The outermost while loop divides the array into two parts. Our goal is to move all smaller elements (smaller than the pivot) to the left part and all greater elements to the right part. Elements equal to the pivot can end up on either side, which is why the pivot doesn’t always land in its final position after one pass.

If the elements to the left of the pivot are less than the pivot element, we skip their positions:

while (array[i] < pivot)
{
    i++;
}

Subsequently, if the elements to the right of the pivot are greater than the pivot element, we skip their positions as we loop through the right subarray:

while (array[j] > pivot)
{
    j--;
}

As we loop through the array, if we find an element in the left subarray that is greater than or equal to the pivot and an element in the right subarray that is less than or equal to the pivot, we swap their positions. SortArray() swaps the positions of array[i] and array[j] and updates the subarrays’ counters accordingly:

if (i <= j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    i++;
    j--;
}

Since the quicksort algorithm is recursive, the method calls itself to sort the left and right subarrays and returns a sorted array when the process is complete:

if (leftIndex < j)
    SortArray(array, leftIndex, j);

if (i < rightIndex)
    SortArray(array, i, rightIndex);

return array;

Finally, in a test method of an MSTest project that references our app, we can verify that the SortArray() method sorts a given unsorted array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1, 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 1, 20, 20, 49, 49, 57, 57, 73, 73, 99, 99, 133, 133 };

var sortFunction = new QuickSortMethods();

var sortedArray = sortFunction.SortArray(array, 0, array.Length - 1);

Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);

Let’s learn quicksort’s time and space complexity and understand why it is considered to be one of the most efficient sorting algorithms.  

Space Complexity of Quicksort Algorithm

As we’ve seen in the implementation section, the quicksort algorithm only needs extra space for handling recursive function calls and temporary variables when swapping array elements. Each recursive call allocates a new stack frame of constant size.

How much stack that takes depends on how deep the recursion goes. When the partitions are roughly balanced, the size of the range halves at every level, and the recursion is about log₂ N calls deep. That gives us a space complexity of O(log N) on average.

When the partitions are lopsided, which is the worst case we’ll meet below, every call peels off just one element and the recursion goes N levels deep. Our implementation recurses into both parts, so in that case its space complexity is O(N).

The usual fix is to recurse into the smaller part and loop over the larger one, which keeps the depth at O(log N) even in the worst case.

Time Complexity of Quicksort Algorithm

Quicksort is a “divide and conquer” algorithm as it subdivides a large unsorted array into smaller partitions that are easily sorted by comparing array elements with their pivots. 

Best-Case Time Complexity

Quicksort achieves optimal performance if we always divide the arrays and subarrays into two partitions of equal size when the pivot is the median of the range. For example, when we want to sort an array that has four elements, we partition it twice since we use recursion to implement the algorithm.

This becomes quicksort’s best-case scenario, which we can explain using this recurrence relation:

T(N) = 2T(N/2) + O(N)

From this relation, we can see that the size of the array is halved each time we partition the array. This means the number of partitioning levels is log₂ N. Therefore since we have N array elements and log₂ N partitioning levels, the best-case scenario of quicksort is O(N log N).

Average-Case Time Complexity

To come up with an accurate depiction of how quicksort handles average-case complexity, we need to consider all the possible array permutations and calculate the time the algorithm takes to sort each array permutation, which is not easy. 

However, since the number of partitioning levels still grows with log N on average, and each level touches N elements, the average-case complexity of the quicksort algorithm is O(N log N).

Worst-Case Time Complexity

This scenario occurs if the selected pivot element is always the smallest or largest element of the array or its partitions. Such a scenario occurs when we keep choosing the first or last element of an array that has been sorted as the pivot element.

The partitioning process splits the array into two non-equal partitions. One partition has a length of zero (no element belongs on that side of the pivot element). The other partition has a length of N-1 ( the rest of the elements except the pivot element).

Therefore, when we calculate the partitioning levels, the algorithm would need N partitioning levels with the partitions having size N, N-1, N-2, etc. 

Quicksort’s worst-case complexity becomes O(N²) as its partitioning effort decreases linearly from N to 0. 

In practice, a large presorted array fails before the quadratic time becomes the problem. Every one of those N partitioning levels is a nested recursive call, and the call stack runs out first.

We tried it on .NET 10 on Windows x64. Our first-element version crashed on a sorted array of 10,000 elements inside BenchmarkDotNet and on a sorted array of 100,000 elements in a plain console app, each time after thousands of nested calls. A StackOverflowException can’t be caught with try/catch. The runtime ends the whole process.

One of the strategies we can use to address this problem is shuffling the array first, for example with Random.Shared.Shuffle(). It introduces randomness in the array, making it possible for the algorithm to work efficiently. The cheaper fix is to choose a better pivot, which is what we’ll do next.

How Do We Keep Quicksort Away From Its Worst Case?

The fix is a one-line change. We take the element in the middle of the range as the pivot instead of the first one:

var pivot = array[leftIndex + (rightIndex - leftIndex) / 2];

Everything else in SortArray() stays the same. In the sample, this version lives next to the original as SortArrayWithMiddlePivot(), and its recursive calls go to SortArrayWithMiddlePivot() as well.

Why does that help? On a sorted array, the middle element is also the median, so every partition splits the range in half and the recursion stays about log₂ N calls deep. The sorted array of 100,000 elements that crashed the first-element version sorts without trouble, and the sample has a test for it.

We write leftIndex + (rightIndex - leftIndex) / 2 instead of (leftIndex + rightIndex) / 2 out of habit. The two give the same result here, but the first one can’t overflow int when both indexes are close to int.MaxValue.

The middle element still has a worst case of its own. A specially built input can make it pick a bad pivot every time. For data that comes from users or other systems, a random pivot or a shuffle first makes that practically impossible.

Advantages of Quicksort Algorithm

To start with, the quicksort algorithm is fast and efficient, especially in best and average-case time complexity scenarios. This makes it better than other algorithms such as selection sort and bubble sort, which have O(N²) time complexity. 

Besides being fast and efficient, quicksort is memory-efficient. This algorithm sorts all the array elements in place, which makes it ideal for use in applications that have limited memory. On the other hand, other algorithms such as merge sort need auxiliary arrays to store values during the sorting process. 

Disadvantages of Quicksort Algorithm

First, quicksort is an unstable algorithm, which means, it may not preserve the original order of key-value pairs. For example, when quicksort encounters two similar elements, their order could be reversed as the algorithm sorts them. Therefore, in situations where stability is an important factor, quicksort may not be the best algorithm to use. 

Besides being unstable, we can see that quicksort has a worst-case complexity of O(N²). Therefore, although the algorithm is fast and efficient in best and average-case scenarios, it is not efficient when it encounters large arrays that are sorted and the pivot is the first or last element.

Performance Tests

Let’s verify the quicksort algorithm has a time complexity of O(N log N) on random data, and see what a sorted array does to it. We are going to accomplish this by measuring the time it takes for the algorithm to sort an array with BenchmarkDotNet. We add the BenchmarkDotNet package to our console app. Its Program.cs holds a single call, BenchmarkRunner.Run<QuickSortBenchmarks>(), with using BenchmarkDotNet.Running; at the top, and we run it in Release mode.

We compare three versions: our first-element pivot, the middle-element pivot from the previous section, and the built-in Array.Sort().

First, let’s add a method to QuickSortMethods to generate a set of random array elements:

public static int[] CreateRandomArray(int size)
{
    var array = new int[size];

    for (int i = 0; i < size; i++)
        array[i] = Random.Shared.Next();

    return array;
}

The CreateRandomArray() method takes an integer as its sole input. Using the shared instance of the inbuilt Random class, we generate integer values that we’re going to put into the array.

Next, we are going to define a method in the same class that generates a sequence of elements. This method simulates a scenario where we have a sorted array:

public static int[] CreateSortedArray(int size)
{
    var array = new int[size];

    for (int i = 0; i < size; i++)
        array[i] = i;

    return array;
}

Our SortArray() sorts the array in place, and BenchmarkDotNet calls the benchmark method many times with the same arguments. If we pass the array straight in, only the first call sees unsorted data. Every call after that sorts an array that is already sorted.

So, we keep the generated array as a source and copy it into a working array at the start of every call:

using BenchmarkDotNet.Attributes;

public class QuickSortBenchmarks
{
    private readonly QuickSortMethods _sorter = new();
    private int[] _source = [];
    private int[] _work = [];

    [Params(200, 1000, 2000)]
    public int Size { get; set; }

    [Params("Unsorted", "Sorted")]
    public string Input { get; set; } = "Unsorted";

    [GlobalSetup]
    public void Setup()
    {
        _source = Input == "Sorted"
            ? QuickSortMethods.CreateSortedArray(Size)
            : QuickSortMethods.CreateRandomArray(Size);
        _work = new int[Size];
    }

    [Benchmark(Baseline = true)]
    public int[] FirstElementPivot()
    {
        _source.CopyTo(_work, 0);
        return _sorter.SortArray(_work, 0, _work.Length - 1);
    }

    [Benchmark]
    public int[] MiddleElementPivot()
    {
        _source.CopyTo(_work, 0);
        return _sorter.SortArrayWithMiddlePivot(_work, 0, _work.Length - 1);
    }

    [Benchmark]
    public int[] ArraySort()
    {
        _source.CopyTo(_work, 0);
        Array.Sort(_work);
        return _work;
    }
}

[Params] gives us every combination of the three sizes and the two kinds of input, and [GlobalSetup] builds the source array once for each method and combination. The copy costs the same in all three methods, so it doesn’t change how they compare.

We stop at 2,000 elements on purpose. With 10,000 sorted elements, the first-element version never finishes: the benchmark process dies with the stack overflow from the Worst-Case section, and BenchmarkDotNet can only print NA for that row.

Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:

| Method             | Size | Input    | Mean         | Error       | StdDev      | Ratio | RatioSD |
|------------------- |----- |--------- |-------------:|------------:|------------:|------:|--------:|
| FirstElementPivot  | 200  | Sorted   |   9,159.2 ns |   114.08 ns |   106.71 ns |  1.00 |    0.02 |
| MiddleElementPivot | 200  | Sorted   |     965.4 ns |    19.24 ns |    17.05 ns |  0.11 |    0.00 |
| ArraySort          | 200  | Sorted   |     547.7 ns |    10.92 ns |    14.19 ns |  0.06 |    0.00 |
|                    |      |          |              |             |             |       |         |
| FirstElementPivot  | 200  | Unsorted |   2,485.3 ns |    45.74 ns |    42.79 ns |  1.00 |    0.02 |
| MiddleElementPivot | 200  | Unsorted |   2,221.6 ns |    43.48 ns |    44.65 ns |  0.89 |    0.02 |
| ArraySort          | 200  | Unsorted |   1,521.2 ns |    19.69 ns |    18.42 ns |  0.61 |    0.01 |
|                    |      |          |              |             |             |       |         |
| FirstElementPivot  | 1000 | Sorted   | 161,000.1 ns | 2,927.07 ns | 2,737.98 ns |  1.00 |    0.02 |
| MiddleElementPivot | 1000 | Sorted   |   5,159.8 ns |    55.40 ns |    51.82 ns |  0.03 |    0.00 |
| ArraySort          | 1000 | Sorted   |   3,402.1 ns |    62.29 ns |    58.27 ns |  0.02 |    0.00 |
|                    |      |          |              |             |             |       |         |
| FirstElementPivot  | 1000 | Unsorted |  15,793.9 ns |   306.93 ns |   399.10 ns |  1.00 |    0.03 |
| MiddleElementPivot | 1000 | Unsorted |  15,325.3 ns |   285.19 ns |   266.76 ns |  0.97 |    0.03 |
| ArraySort          | 1000 | Unsorted |  10,067.4 ns |   197.63 ns |   227.59 ns |  0.64 |    0.02 |
|                    |      |          |              |             |             |       |         |
| FirstElementPivot  | 2000 | Sorted   | 587,519.9 ns | 9,491.47 ns | 8,878.32 ns |  1.00 |    0.02 |
| MiddleElementPivot | 2000 | Sorted   |  10,791.2 ns |   207.33 ns |   193.93 ns |  0.02 |    0.00 |
| ArraySort          | 2000 | Sorted   |   7,302.1 ns |   146.06 ns |   150.00 ns |  0.01 |    0.00 |
|                    |      |          |              |             |             |       |         |
| FirstElementPivot  | 2000 | Unsorted |  75,602.0 ns | 1,405.66 ns | 2,103.92 ns |  1.00 |    0.04 |
| MiddleElementPivot | 2000 | Unsorted |  54,428.5 ns | 1,868.25 ns | 5,508.59 ns |  0.72 |    0.08 |
| ArraySort          | 2000 | Unsorted |  53,995.4 ns | 1,064.62 ns | 1,593.48 ns |  0.71 |    0.03 |

On random data, going from 200 to 1,000 elements, five times the size, takes our first-element version about 6.4 times as long, close to the 6.5 that O(N log N) predicts. From 1,000 to 2,000 elements, all three versions grow faster than that in this run, Array.Sort() included: between 3.5 and 5.4 times as long for twice the size. Array.Sort() is the fastest in every row except 2,000 random elements, where the middle-element pivot ties with it within the margin of error. Our own versions stay within the same order of magnitude.

On 2,000 sorted elements, the first-element pivot is about 54 times slower than the middle-element pivot. This is the O(N²) worst case from the previous sections.

The middle-element pivot sorts the sorted arrays faster than the random ones, because every partition splits the range in half and no element has to move.

Should We Write Our Own Quicksort or Use Array.Sort()?

In production code, we should use Array.Sort(), or Span<T>.Sort() and List<T>.Sort(), which run the same algorithm. Our own quicksort is for learning how the algorithm works.

Array.Sort() is quicksort with its weak spots patched. Microsoft Learn says plainly that “This method uses the introspective sort (introsort) algorithm”. It uses quicksort for most of the work, switches to insertion sort for partitions of 16 elements or fewer, and falls back to heapsort when the recursion gets too deep.

Our version is missing that last rule. Introsort’s worst case stays O(N log N), and a sorted array can’t crash it.

In our benchmark, Array.Sort() was the fastest on random and sorted input alike, apart from a tie with the middle-element pivot on 2,000 random elements.

Like our quicksort, Array.Sort() is unstable: equal elements may change their order. When the order of equal keys matters, LINQ’s OrderBy() is the stable choice.

We cover insertion sort and heapsort in their own articles, and the stable and unstable ways of sorting a list by a property in a separate one.

Conclusion

In this article, we have learned how quicksort works in C#. It uses recursion and the “divide and conquer” strategy to make it efficient. Just like the other algorithms, it has some strengths and weaknesses.

The biggest weakness is the pivot. With the first element as the pivot, a sorted array pushes quicksort into its O(N²) worst case and, on a large enough array, crashes the process with a stack overflow. Taking the middle element fixes that for sorted data with a one-line change.

For real applications, Array.Sort() already gives us quicksort with those problems solved. Our own version is still worth writing once, to see what Array.Sort() does for us.

Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.