/// <summary>
/// An in-place quicksort implementation based on the Hoare partition scheme.
/// </summary>
/// <typeparam name="T">The type of the elements being sorted.</typeparam>
/// <param name="input">A span of elements to be sorted.</param>
public static void Quicksort<T>(Span<T> input) where T : IComparable<T>
{
    Quicksort<T>(input, Comparer<T>.Default);
}

/// <summary>
/// An in-place quicksort implementation based on the Hoare partition scheme.
/// </summary>
/// <typeparam name="T">The type of the elements being sorted.</typeparam>
/// <param name="input">A span of elements to be sorted.</param>
/// <param name="comparer">The comparer to use when comparing the elements.</param>
public static void Quicksort<T>(Span<T> input, IComparer<T> comparer)
{
    if (input.Length <= 1) { return; } // Base case

    T pivot = input[(input.Length - 1) / 2];

    int i = -1;
    int j = input.Length;

    while (true)
    {
        while (comparer.Compare(input[++i], pivot) < 0) ;
        while (comparer.Compare(input[--j], pivot) > 0) ;

        if (i >= j)
        {
            Quicksort(input.Slice(0, j + 1), comparer);
            if (j + 1 < input.Length) Quicksort(input.Slice(j + 1), comparer);
            return;
        }

        T temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}