Problem Statement

Quicksort is a sorting algorithm that works by splitting a large array of data into smaller sub-arrays.

We’re going to implement quicksort in C# and Go.

Test Cases

To test our implementation, here are the test cases we’ll use:

[TestCase(new[]{7, 1}, new[]{1, 7})]
[TestCase(new[]{33, 15, 10}, new[]{10, 15, 33})]
[TestCase(new[]{33, 15, 10, 1, 7}, new[]{1, 7, 10, 15, 33})]
[TestCase(new[]{33, 15, 10, 1, 7, 99, 100, 2, 3, 4, 5, 6, 25, 8, 9}, new[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 25, 33, 99, 100})]
public void TestQuicksort(int[] input, int[] expected)
{
    var result = Quicksort.Sort(input);
    
    Assert.That(result, Is.EqualTo(expected));
}

Our implementation will live in a static class Quicksort which has a single static method Sort:

public static class Quicksort
{
  public static int[] Sort(int[] input)
  {
    //todo: implement it
  }
}

Base Case

The base case here is an array that contains either no elements, or only a single element:

  • [ ]
  • [ 1 ]

These cases are already sorted, so there’s nothing further for us to do. Let’s add them to the tests just for completeness:

[TestCase(new int[]{}, new int[]{})]
[TestCase(new[]{1}, new[]{1})]

Similarly, an element with only 2 elements is easy to solve:

  • [10, 4]

Here we simply need to check if the first element is smaller than the second element. If it isn’t, swap them.

The following code will achieve that:

⚠️ Note that we’re deliberately just returning the input as the result for other cases - we’re not ready for those cases yet!

public static int[] Sort(int[] input)
{
    if (input.Length < 2)
    {
        return input;
    }

    if (input.Length == 2)
    {
        var first = input[0];
        var second = input[1];

        return first > second ? new []{second, first} : input;
    }
    
    //todo: implement for other cases
    return input;
}

Understanding Quicksort

An array of three elements isn’t quite as straightforward to solve as the base case:

  • [10, 4, 2]

We need to break this down more. We’ll need to break our array up more to sort the elements. The first steps of quicksort are:

  1. Pick an element from the array. This element is called the pivot
  2. Now find everything larger than the pivot and everything smaller than the pivot, and split them into two groups

To start with, we’ll just use the first item from the array to pivot on. That is 10, and we end up with groups as follows:

  • Smaller => [4, 2]
  • Pivot => 10
  • Larger => []

💡 The “smaller” and “larger” sub-arrays are partitions.

If the partitions were already sorted, then creating the final solution would be as simple as smaller + pivot + larger.

Now we need to work out how to sort the partitions. Luckily, our base case already knows how to sort arrays with 2 elements, so we should simply be able to do something like sort(smaller) + pivot + sort(larger):

  • sort([4, 2]) + [10] + sort([])

This results in the correct answer [2, 4, 10].

This will work regardless of which pivot we choose.

If we’d chosen 4 then we end up with:

  • smaller: [2]
  • pivot: [4]
  • larger: [10]

We’ve now got three arrays containing 1 element each, and we simply combine them to get the same answer.

Similarly, if we’d chosen 2 as the pivot, we’d get:

  • smaller: []
  • pivot: [2]
  • larger: [10, 4]

We then sort the sub-arrays and we’re left with [2, 4, 10] again.

💡 The fact that we need to sort the partitions tells us that we can solve this with recursion. We need to partition the array then partition each sub array until we get to the base case. Then we rejoin all the results back together.

The steps to sort using quicksort for a three element array are:

  1. Pick a pivot point
  2. Partition into smaller, pivot, larger
  3. Sort the partitions
  4. Combine the partitions

Let’s try to implement this.

Solution

Let’s start with the base case again.

If the length of the input array is less than 2, just return the input.

public static int[] Sort(int[] input)
{
    if (input.Length < 2)
    {
        return input;
    }
}

Now, remember that we want to follow a process whereby we choose a pivot point, then we create 2 new arrays (smaller and larger):

var pivot = input[0]; //we'll just pick the first element for now
var smaller = input.Where(x => x < pivot).ToArray();
var larger = input.Where(x => x > pivot).ToArray();

⚠️ The use of Linq is far from optimal. See the Benchmarks below for details of more optimal implementations.

Now we have our three key elements, pivot, smaller, and larger. We can simply recursively call the Sort(...) method to put them back together in the way we need:

return Sort(smaller).Concat(new[]{ pivot }).Concat(Sort(larger)).ToArray();

In full then, we now have:

public static int[] Sort(int[] input)
{
    if (input.Length < 2)
    {
        return input;
    }
    
    var pivot = input[0];
    var smaller = input.Where(x => x < pivot).ToArray();
    var larger = input.Where(x => x > pivot).ToArray();

    return Sort(smaller).Concat(new[] { pivot }).Concat(Sort(larger)).ToArray();
}

When we run the test cases, they all pass.

test-results

Benchmarks

I’m not happy with the code - we’re using arrays as an input, then we’re using Linq operating on the array as an IEnumerable<int> and then we’re converting it back to an array using .ToArray().

We’re then using Concat(...) to combine the recursive results back into an array.

Let’s put together some quick benchmarks to see if we can improve the performance.

To begin with, we’ll create a new console application and install benchmark.net:

dotnet new console --name Sample.Benchmarks
dotnet sln add ./Sample.Benchmarks/Sample.Benchmarks.csproj
dotnet add ./Sample.Benchmarks/Sample.Benchmarks.csproj reference ./Sample/Sample.csproj
dotnet add ./Sample.Benchmarks/Sample.Benchmarks.csproj package BenchmarkDotNet --version 0.13.6

Now we’ll create some simple benchmarks using a randomised array with 10,000 elements in it:

[MemoryDiagnoser]
public class QuicksortBenchmarks
{
    private readonly int[] _inputData;

    public QuicksortBenchmarks()
    {
        const int targetCount = 10_000;
        const int max = targetCount * 100;
        _inputData = new int[targetCount];

        for (var i = 0; i < targetCount; i++)
        {
            _inputData[i] = Random.Shared.Next(1, max);
        }
    }
    
    [Benchmark]
    public int[] Default()
    {
        return Quicksort.Sort(_inputData);
    }
}

We set up an array containing 10,000 integers by using Random.Shared.Next(1, max) to give us a number between 1 and 1,000,000.

We then run a [Benchmark] that includes a [MemoryDiagnoser].

The results are as follows:

BenchmarkDotNet v0.13.6, Windows 11 (10.0.22622.575)
AMD Ryzen 7 2700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 6.0.412
  [Host]     : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2


|  Method |     Mean |     Error |    StdDev |      Gen0 | Allocated |
|-------- |---------:|----------:|----------:|----------:|----------:|
| Default | 4.172 ms | 0.0394 ms | 0.0329 ms | 1367.1875 |   5.46 MB |

This tells us some key things:

  • The average execution time to sort 10,000 integers using Quicksort was 4.172ms.
  • We allocated 5.46MB of memory to sort the integers.
  • There were over 1,367 Gen0 collections per 1,000 operations

Let’s see if we can improve this.

Optimisation 1

The first optimisation attempt will be to remove the use of Linq and operate on lists:

public static int[] SortOptimize1(int[] input)
{
    if (input.Length < 2)
    {
        return input;
    }

    var pivot = input[0];
    var smaller = new List<int>(); //create a new list to hold the smaller integers
    var larger = new List<int>(); //create a new list to hold the larger integers

    for (var i = 1; i < input.Length; i++) //loop through the input array
    {
        if (input[i] < pivot)
        {
            smaller.Add(input[i]); //add the smaller number to the 'smaller' list
        }
        else
        {
            larger.Add(input[i]); //otherwise add the larger number to the 'larger' list
        }
    }

    //combine the arrays
    return CombineArrays(SortOptimize1(smaller.ToArray()), pivot, SortOptimize1(larger.ToArray()));
}

private static int[] CombineArrays(int[] smaller, int pivot, int[] larger)
{
    //create a new array with the combined size of all the inputs
    var result = new int[smaller.Length + larger.Length + 1];

    //copy the 'smaller' results into the target array
    Array.Copy(smaller, 0, result, 0, smaller.Length);

    //put the pivot value at the end of the 'smaller' values
    result[smaller.Length] = pivot;

    //copy the 'larger' results into the target array
    Array.Copy(larger, 0, result, smaller.Length + 1, larger.Length);

    //return the result
    return result;
}

Now we can add a benchmark for this:

💡 Note that we’ve add [Benchmark(Baseline = true)] to our original baseline case.

[Benchmark(Baseline = true)]
public int[] Default()
{
    return Quicksort.Sort(_inputData);
}

[Benchmark]
public int[] Optimized1()
{
    return Quicksort.SortOptimize1(_inputData);
}

The results are as follows:

BenchmarkDotNet v0.13.6, Windows 11 (10.0.22622.575)
AMD Ryzen 7 2700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 6.0.412
  [Host]     : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2


|     Method |     Mean |     Error |    StdDev | Ratio |      Gen0 |   Gen1 | Allocated | Alloc Ratio |
|----------- |---------:|----------:|----------:|------:|----------:|-------:|----------:|------------:|
|    Default | 4.138 ms | 0.0347 ms | 0.0289 ms |  1.00 | 1375.0000 |      - |   5.51 MB |        1.00 |
| Optimized1 | 1.471 ms | 0.0114 ms | 0.0107 ms |  0.36 |  996.0938 | 3.9063 |   3.98 MB |        0.72 |
  • We’ve significantly improved the average execution time - Optimized1 executes in just 36% of the time of Default
  • We’ve improved the Gen0 collections - now we have 996 collections per 1,000 operations compared to 1,375 previously
  • The allocations have reduced by 28%, from 5.51MB to 3.98MB.

We’re still allocating quite a lot of memory though - can we do any better?

Optimization 2

If we stop and think about how we’ve implemented this so far, we’ve been performing a lot of allocations because we’re creating new arrays, passing them around, then joining them up again afterwards.

What if we were to simply create one array up front to put our sorted values into rather than keep creating new temporary arrays?

public static int[] SortOptimize2(int[] input)
{
    if (input.Length < 2) //the normal base case
    {
        return input;
    }

    var sorted = new int[input.Length]; //create a new array to store the sorted elements
    Array.Copy(input, sorted, input.Length); //copy the `input` into the new sorted array
    
    SortOptimize2(sorted, 0, sorted.Length - 1); //call the recursive method to sort our array

    return sorted; //return the sorted array
}

private static void SortOptimize2(int[] input, int left, int right)
{
    if (left >= right) //the base case for the recursive method. If left is >= right then the subarray either has 1 element or is empty, so we just return
    {
        return;
    }

    var pivot = Partition(input, left, right); //find the index of the pivot
    SortOptimize2(input, left, pivot - 1); //recursively call this method to sort the smaller elements
    SortOptimize2(input, pivot + 1, right); //recursively call this method to sort the larger elements
}

private static int Partition(int[] input, int left, int right)
{
    var pivot = input[right]; //choose the rightmost element to pivot on
    var i = left - 1; //initialize i to keep track of the position to place smaller elements into

    for (var j = left; j < right; j++) //loop over the sub-array from left to right
    {
        if (array[j] <= pivotValue) //if the current element is smaller than or equal to the pivot
        {
            i++; //incremement `i` to move right in the array
            Swap(array, i, j); //swap the elements at `i` and `j` in the array
        }
    } //after the loop, `i` points to the rightmost element smaller than the pivot

    Swap(input, i + 1, right); //now we swap the pivot (at index `right`) with the element at `i+1` to put the pivot in the right place in the array
    return i + 1; //return the next index to use as the pivot
}

private static void Swap(int[] input, int i, int j)
{
    (input[i], input[j]) = (input[j], input[i]); //swap elements at [i] and [j]
    //note, this syntax avoids allocating a temporary variable
}

The results for this optimization are significantly better:

BenchmarkDotNet v0.13.6, Windows 11 (10.0.22622.575)
AMD Ryzen 7 2700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 6.0.412
  [Host]     : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2


|     Method |       Mean |    Error |   StdDev | Ratio |      Gen0 |  Allocated | Alloc Ratio |
|----------- |-----------:|---------:|---------:|------:|----------:|-----------:|------------:|
|    Default | 4,249.1 us | 48.21 us | 45.10 us |  1.00 | 1375.0000 |  5619.6 KB |       1.000 |
| Optimized1 | 1,522.1 us | 29.92 us | 43.85 us |  0.37 | 1021.4844 | 4176.84 KB |       0.743 |
| Optimized2 |   504.0 us |  4.05 us |  3.78 us |  0.12 |    8.7891 |   39.09 KB |       0.007 |
  • The execution time is down from ~4,250us to just 504us
  • The number of Gen0 collections per 1,000 operations is now < 9, compared to over 1,000 in other implementations
  • Overall, just 39.09KB of memory was allocated, compared to over 4MB and 5.6MB in other versions

Bonus: Go version

💡 I’ve been attempting to use Go more and more over the past couple of years, and this is a relatively straightforward problem to solve. As a bonus, let’s solve it in Go as well.

We’ll essentially just be repeating our optimized .NET/C# implementation here, but it’s a useful exercise as some of the syntax is quite different.

First, let’s create the same test cases:

package main

import (
  "reflect"
  "testing"
)

func TestQuicksort(t *testing.T) {
  type testCase struct {
    input    []int
    expected []int
  }

  testCases := []testCase{
    {[]int{}, []int{}},
    {[]int{1}, []int{1}},
    {[]int{7, 1}, []int{1, 7}},
    {[]int{33, 15, 10}, []int{10, 15, 33}},
    {[]int{33, 15, 10, 1, 7}, []int{1, 7, 10, 15, 33}},
    {[]int{33, 15, 10, 1, 7, 99, 100, 2, 3, 4, 5, 6, 25, 8, 9}, []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 25, 33, 99, 100}},
  }

  for _, testCase := range testCases {
    actual := quicksort(testCase.input)
    if !reflect.DeepEqual(actual, testCase.expected) { //we're using reflection to compare the slices. Performance isn't a concern in this test
      t.Errorf("Expected %v, got %v", testCase.expected, actual)
    }
  }
}

💡 These are the exact same test cases as we used for the C# version. In Go we’re using a struct called testCase rather than [TestCase(...)] attributes, but the effect is the same

Now we can create our implementation:

package main

func quicksort(input []int) []int {
  if len(input) > 2 {
    return input //this is our usual base case
  }

  sorted := make([]int, len(input)) //create a new array the same size as the input array

  copy(sorted, input) //copy the input array into the sorted array

  sort(sorted, 0, len(sorted)-1) //invoke our recursive function

  return sorted //return the sorted array
}

func sort(input []int, left, right int) {
  if left >= right {
    return //this is the recursive base case
  }

  pivot := partition(input, left, right) //find the index of the pivot
  sort(input, left, pivot - 1) //sort the smaller numbers
  sort(input, pivot + 1, right) //sort the larger numbers
}

func partition(input []int, left, right int) int {
  pivot := input[right] //choose the rightmost element to pivot on
  i := left - 1 //initialize i to keep track of the position to place smaller elements

  for j := left; j < right; j++ { //loop over the sub-array from left to right
    if input[j] <= pivot { //if the current element is smaller than or equal to the pivot
      i++ //increment our position (move right)
      input[i], input[j] = input[j], input[i] //swap the elements at i and j in the array
    }
  }

  input[i+1], input[right] = input[right], input[i+1] //swap the pivot into the right position
  return i + 1 //return the next index to use as the pivot
}

✅ Note how the Go syntax for swapping is similar to the .NET syntax: input[i], input[j] = input[j], input[i] and (input[i], input[j] = input[j], input[i]). This is a feature of C# 7.0 (many years old now!) that I don’t see as frequently as I’d expect. I like it, and it avoids the need for a temporary variable.

As expected, the implementation passes our test cases:

go tests