PdqSort C# Port

pdqsort_benchmark.cs

// PdqSort: https://github.com/orlp/pdqsort

using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Environments;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

namespace SortBench;

[Config(typeof(Config))]
public class SortBenchTest
{
    // Partitions below this size are sorted using insertion sort.
    const int InsertionSortThreshold = 24;
    // Partitions above this size use Tukey's ninther to select the pivot.
    const int NintherThreshold = 128;
    // When we detect an already sorted partition, attempt an insertion sort that allows this
    // amount of element moves before giving up.
    const int PartialInsertionSortLimit = 8;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static ref T UnguardedAccess<T>(Span<T> span, int index)
    {
        return ref Unsafe.Add(ref MemoryMarshal.GetReference(span), index);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static Span<T> UnguardedSlice<T>(Span<T> span, int begin, int end)
    {
        return MemoryMarshal.CreateSpan(ref UnguardedAccess(span, begin), end - begin);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static bool Compare<T>(T left, T right, IComparer<T> comparer)
    {
        return comparer.Compare(left, right) < 0;
    }

    static void HeapSort<T>(Span<T> span, IComparer<T> comparer)
    {
        if (span.Length == 0) return;
        int n = span.Length;
        for (int i = n >> 1; i >= 1; i--)
        {
            DownHeap(span, i, n, comparer);
        }

        for (int i = n; i > 1; i--)
        {
            Swap(ref UnguardedAccess(span, 0), ref UnguardedAccess(span, i - 1));
            DownHeap(span, 1, i - 1, comparer);
        }
    }

    static void DownHeap<T>(Span<T> span, int i, int n, IComparer<T> comparer)
    {
        T d = UnguardedAccess(span, i - 1);
        while (i <= n >> 1)
        {
            int child = 2 * i;
            if (child < n && Compare(UnguardedAccess(span, child - 1), UnguardedAccess(span, child), comparer))
            {
                child++;
            }

            if (!Compare(d, UnguardedAccess(span, child - 1), comparer))
                break;

            UnguardedAccess(span, i - 1) = UnguardedAccess(span, child - 1);
            i = child;
        }

        UnguardedAccess(span, i - 1) = d;
    }

    // Sorts [begin, end) using insertion sort with the given comparison function.
    static void InsertionSort<T>(Span<T> span, int begin, int end, IComparer<T> comparer)
    {
        if (begin == end) return;
        for (var i = begin + 1; i < end; i++)
        {
            var sift = i;
            var sift1 = i - 1;

            // Compare first so we can avoid 2 moves for an element already positioned correctly.
            if (Compare(UnguardedAccess(span, sift), UnguardedAccess(span, sift1), comparer))
            {
                var tmp = UnguardedAccess(span, sift);
                do
                {
                    UnguardedAccess(span, sift--) = UnguardedAccess(span, sift1);
                }
                while (sift != begin && Compare(tmp, UnguardedAccess(span, --sift1), comparer));

                UnguardedAccess(span, sift) = tmp;
            }
        }
    }

    // Sorts [begin, end) using insertion sort with the given comparison function. Assumes
    // *(begin - 1) is an element smaller than or equal to any element in [begin, end).
    static void UnguardedInsertionSort<T>(Span<T> span, int begin, int end, IComparer<T> comparer)
    {
        if (begin == end) return;
        for (var i = begin + 1; i < end; i++)
        {
            var sift = i;
            var sift1 = i - 1;

            // Compare first so we can avoid 2 moves for an element already positioned correctly.
            if (Compare(UnguardedAccess(span, sift), UnguardedAccess(span, sift1), comparer))
            {
                var tmp = UnguardedAccess(span, sift);
                do
                {
                    UnguardedAccess(span, sift--) = UnguardedAccess(span, sift1);
                }
                while (Compare(tmp, UnguardedAccess(span, --sift1), comparer));

                UnguardedAccess(span, sift) = tmp;
            }
        }
    }

    // Attempts to use insertion sort on [begin, end). Will return false if more than
    // partial_insertion_sort_limit elements were moved, and abort sorting. Otherwise it will
    // successfully sort and return true.
    static bool PartialInsertionSort<T>(Span<T> span, int begin, int end, IComparer<T> comparer)
    {
        if (begin == end) return true;
        var limit = 0;
        for (var i = begin + 1; i < end; i++)
        {
            var sift = i;
            var sift1 = i - 1;

            // Compare first so we can avoid 2 moves for an element already positioned correctly.
            if (Compare(UnguardedAccess(span, sift), UnguardedAccess(span, sift1), comparer))
            {
                var tmp = UnguardedAccess(span, sift);
                do
                {
                    UnguardedAccess(span, sift--) = UnguardedAccess(span, sift1);
                }
                while (sift != begin && Compare(tmp, UnguardedAccess(span, --sift1), comparer));

                UnguardedAccess(span, sift) = tmp;
                limit += i - sift;
            }

            if (limit > PartialInsertionSortLimit) return false;
        }

        return true;
    }

    // Partitions [begin, end) around pivot *begin using comparison function comp. Elements equal
    // to the pivot are put in the right-hand partition. Returns the position of the pivot after
    // partitioning and whether the passed sequence already was correctly partitioned. Assumes the
    // pivot is a median of at least 3 elements and that [begin, end) is at least
    // insertion_sort_threshold long.
    static (int Pivot, bool HasPartitioned) PartitionRight<T>(Span<T> span, int begin, int end, IComparer<T> comparer)
    {
        // Move pivot into local for speed.
        var pivot = UnguardedAccess(span, begin);
        var first = begin;
        var last = end;

        // Find the first element greater than or equal than the pivot (the median of 3 guarantees
        // this exists).
        while (Compare(UnguardedAccess(span, ++first), pivot, comparer)) ;

        // Find the first element strictly smaller than the pivot. We have to guard this search if
        // there was no element before *first.
        if (first - 1 == 0) while (first < last && !Compare(UnguardedAccess(span, --last), pivot, comparer)) ;
        else while (!Compare(UnguardedAccess(span, --last), pivot, comparer)) ;

        // If the first pair of elements that should be swapped to partition are the same element,
        // the passed in sequence already was correctly partitioned.
        bool hasPartitioned = first >= last;

        // Keep swapping pairs of elements that are on the wrong side of the pivot. Previously
        // swapped pairs guard the searches, which is why the first iteration is special-cased
        // above.
        while (first < last)
        {
            Swap(ref UnguardedAccess(span, first), ref UnguardedAccess(span, last));
            while (Compare(UnguardedAccess(span, ++first), pivot, comparer)) ;
            while (!Compare(UnguardedAccess(span, --last), pivot, comparer)) ;
        }

        // Put the pivot in the right place.
        var pivotPosition = first - 1;
        UnguardedAccess(span, begin) = UnguardedAccess(span, pivotPosition);
        UnguardedAccess(span, pivotPosition) = pivot;

        return (pivotPosition, hasPartitioned);
    }

    // Similar function to the one above, except elements equal to the pivot are put to the left of
    // the pivot and it doesn't check or return if the passed sequence already was partitioned.
    // Since this is rarely used (the many equal case), and in that case pdqsort already has O(n)
    // performance, no block quicksort is applied here for simplicity.
    static int PartitionLeft<T>(Span<T> span, int begin, int end, IComparer<T> comparer)
    {
        var pivot = UnguardedAccess(span, begin);
        var first = begin;
        var last = end;

        while (Compare(pivot, UnguardedAccess(span, --last), comparer)) ;
        if (last + 1 == end) while (first < last && !Compare(pivot, UnguardedAccess(span, ++first), comparer)) ;
        else while (!Compare(pivot, UnguardedAccess(span, ++first), comparer)) ;

        while (first < last)
        {
            Swap(ref UnguardedAccess(span, first), ref UnguardedAccess(span, last));
            while (Compare(pivot, UnguardedAccess(span, --last), comparer)) ;
            while (!Compare(pivot, UnguardedAccess(span, ++first), comparer)) ;
        }

        var pivotPosition = last;
        UnguardedAccess(span, begin) = UnguardedAccess(span, pivotPosition);
        UnguardedAccess(span, pivotPosition) = pivot;

        return pivotPosition;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static void Sort2<T>(ref T a, ref T b, IComparer<T> comparer)
    {
        if (Compare(b, a, comparer))
        {
            Swap(ref a, ref b);
        }
    }

    // Sorts the elements *a, *b and *c using comparison function comp.
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static void Sort3<T>(ref T a, ref T b, ref T c, IComparer<T> comparer)
    {
        Sort2(ref a, ref b, comparer);
        Sort2(ref b, ref c, comparer);
        Sort2(ref a, ref b, comparer);
    }

    static void PdqSort<T>(Span<T> span, int begin, int end, IComparer<T> comparer, int badAllowed, bool leftmost = true)
    {
        while (true)
        {
            var size = end - begin;

            // Insertion sort is faster for small arrays.
            if (size < InsertionSortThreshold)
            {
                if (leftmost) InsertionSort(span, begin, end, comparer);
                else UnguardedInsertionSort(span, begin, end, comparer);
                return;
            }

            // Choose pivot as median of 3 or pseudomedian of 9.
            var mid = size / 2;
            if (size > NintherThreshold)
            {
                Sort3(ref UnguardedAccess(span, begin), ref UnguardedAccess(span, begin + mid), ref UnguardedAccess(span, end - 1), comparer);
                Sort3(ref UnguardedAccess(span, begin + 1), ref UnguardedAccess(span, begin + mid - 1), ref UnguardedAccess(span, end - 2), comparer);
                Sort3(ref UnguardedAccess(span, begin + 2), ref UnguardedAccess(span, begin + mid + 1), ref UnguardedAccess(span, end - 3), comparer);
                Sort3(ref UnguardedAccess(span, begin + mid - 1), ref UnguardedAccess(span, begin + mid), ref UnguardedAccess(span, begin + mid + 1), comparer);
                Swap(ref UnguardedAccess(span, begin), ref UnguardedAccess(span, begin + mid));
            }
            else
            {
                Sort3(ref UnguardedAccess(span, begin + mid), ref UnguardedAccess(span, begin), ref UnguardedAccess(span, end - 1), comparer);
            }

            // If *(begin - 1) is the end of the right partition of a previous partition operation
            // there is no element in [begin, end) that is smaller than *(begin - 1). Then if our
            // pivot compares equal to *(begin - 1) we change strategy, putting equal elements in
            // the left partition, greater elements in the right partition. We do not have to
            // recurse on the left partition, since it's sorted (all equal).
            if (!leftmost && !Compare(UnguardedAccess(span, begin - 1), UnguardedAccess(span, begin), comparer))
            {
                begin = PartitionLeft(span, begin, end, comparer) + 1;
                continue;
            }

            var (pivot, hasPartitioned) = PartitionRight(span, begin, end, comparer);

            // Check for a highly unbalanced partition.
            var leftSize = pivot - begin;
            var rightSize = end - (pivot + 1);
            var highlyUnbalanced = leftSize < size / 8 || rightSize < size / 8;

            // If we got a highly unbalanced partition we shuffle elements to break many patterns.
            if (highlyUnbalanced)
            {
                // If we had too many bad partitions, switch to heapsort to guarantee O(n log n).
                if (--badAllowed == 0)
                {
                    HeapSort(UnguardedSlice(span, begin, end), comparer);
                    return;
                }

                if (leftSize >= InsertionSortThreshold)
                {
                    Swap(ref UnguardedAccess(span, begin), ref UnguardedAccess(span, begin + leftSize / 4));
                    Swap(ref UnguardedAccess(span, pivot - 1), ref UnguardedAccess(span, pivot - leftSize / 4));

                    if (leftSize > NintherThreshold)
                    {
                        Swap(ref UnguardedAccess(span, begin + 1), ref UnguardedAccess(span, begin + leftSize / 4 + 1));
                        Swap(ref UnguardedAccess(span, begin + 2), ref UnguardedAccess(span, begin + leftSize / 4 + 2));
                        Swap(ref UnguardedAccess(span, pivot - 2), ref UnguardedAccess(span, pivot - (leftSize / 4 + 1)));
                        Swap(ref UnguardedAccess(span, pivot - 3), ref UnguardedAccess(span, pivot - (leftSize / 4 + 2)));
                    }
                }

                if (rightSize >= InsertionSortThreshold)
                {
                    Swap(ref UnguardedAccess(span, pivot + 1), ref UnguardedAccess(span, pivot + 1 + rightSize / 4));
                    Swap(ref UnguardedAccess(span, end - 1), ref UnguardedAccess(span, end - rightSize / 4));

                    if (rightSize > NintherThreshold)
                    {
                        Swap(ref UnguardedAccess(span, pivot + 2), ref UnguardedAccess(span, pivot + 2 + rightSize / 4));
                        Swap(ref UnguardedAccess(span, pivot + 3), ref UnguardedAccess(span, pivot + 3 + rightSize / 4));
                        Swap(ref UnguardedAccess(span, end - 2), ref UnguardedAccess(span, end - (1 + rightSize / 4)));
                        Swap(ref UnguardedAccess(span, end - 3), ref UnguardedAccess(span, end - (2 + rightSize / 4)));
                    }
                }
            }
            else
            {
                // If we were decently balanced and we tried to sort an already partitioned
                // sequence try to use insertion sort.
                if (hasPartitioned &&
                    PartialInsertionSort(span, begin, pivot, comparer) &&
                    PartialInsertionSort(span, pivot + 1, end, comparer))
                {
                    return;
                }
            }

            // Sort the left partition first using recursion and do tail recursion elimination for
            // the right-hand partition.
            PdqSort(span, begin, pivot, comparer, badAllowed, leftmost);
            begin = pivot + 1;
            leftmost = false;
        }
    }

    static void Sort<T>(T[] array, IComparer<T> comparer)
    {
        PdqSort(array, 0, array.Length, comparer, BitOperations.Log2((uint)array.Length));
    }

    static IEnumerable<int> GetRandomSequence(int count, bool near)
    {
        while (count-- > 0) yield return near ? Random.Shared.Next(0, count / 4) : Random.Shared.Next();
    }

    static IEnumerable<int> GetReverseSequence(int count)
    {
        while (count-- > 0) yield return count;
    }

    static IEnumerable<int> GetOrderSequence(int count)
    {
        var i = 0;
        while (count-- > 0) yield return i++;
    }

    static IEnumerable<int> GetPeekSequence(int count)
    {
        var mid = count / 2;
        var i = 0;
        while (mid-- > 0)
        {
            count--;
            yield return i++;
        }
        while (count-- > 0) yield return i--;
    }

    static IEnumerable<int> GetReversePeekSequence(int count)
    {
        var mid = count / 2;
        while (mid-- > 0)
        {
            count--;
            yield return mid;
        }
        var i = 0;
        while (count-- > 0) yield return i++;
    }

    [Params(10, 100, 1000, 10000, 100000, 1000000)]
    public int size;

    [GlobalSetup]
    public void GlobalSetup()
    {
        a_allEqual = new int[size];
        p_allEqual = new int[size];
        a_randomNear = new int[size];
        p_randomNear = new int[size];
        a_random = new int[size];
        p_random = new int[size];
        a_sequence = new int[size];
        p_sequence = new int[size];
        a_reverse = new int[size];
        p_reverse = new int[size];
        a_peek = new int[size];
        p_peek = new int[size];
        a_reversePeek = new int[size];
        p_reversePeek = new int[size];

        allEqual = Enumerable.Repeat(1, size).ToArray();
        randomNear = GetRandomSequence(size, true).ToArray();
        random = GetRandomSequence(size, false).ToArray();
        sequence = GetOrderSequence(size).ToArray();
        reverse = GetReverseSequence(size).ToArray();
        peek = GetPeekSequence(size).ToArray();
        reversePeek = GetReversePeekSequence(size).ToArray();
    }

    [IterationSetup]
    public void InitIteration()
    {
        allEqual.CopyTo(a_allEqual, 0);
        allEqual.CopyTo(p_allEqual, 0);
        random.CopyTo(a_random, 0);
        random.CopyTo(p_random, 0);
        randomNear.CopyTo(a_randomNear, 0);
        randomNear.CopyTo(p_randomNear, 0);
        sequence.CopyTo(a_sequence, 0);
        sequence.CopyTo(p_sequence, 0);
        reverse.CopyTo(a_reverse, 0);
        reverse.CopyTo(p_reverse, 0);
        peek.CopyTo(a_peek, 0);
        peek.CopyTo(p_peek, 0);
        reversePeek.CopyTo(a_reversePeek, 0);
        reversePeek.CopyTo(p_reversePeek, 0);
    }

    private int[] allEqual, randomNear, random, sequence, reverse, peek, reversePeek;
    private int[] a_allEqual, a_randomNear, a_random, a_sequence, a_reverse, a_peek, a_reversePeek;
    private int[] p_allEqual, p_randomNear, p_random, p_sequence, p_reverse, p_peek, p_reversePeek;

    class Config : ManualConfig
    {
        public Config()
        {
            AddJob(Job.Default
                .WithMaxIterationCount(10000)
                .WithMinWarmupCount(2000)
                .WithMaxWarmupCount(10000)
                .WithEnvironmentVariable("DOTNET_TieredPgo", "1")
                .WithRuntime(CoreRuntime.CreateForNewVersion("net7.0", ".NET 7.0")));
        }
    }

    static void Main(string[] args)
    {
        BenchmarkRunner.Run<SortBenchTest>(null, args);
    }

    struct MyComparer<T> : IComparer<T>
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Compare(T? x, T? y)
        {
            return Comparer<T>.Default.Compare(x, y);
        }
    }

    [Benchmark]
    public void ArraySort_AllEqual()
    {
        Array.Sort(a_allEqual, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_AllEqual()
    {
        Sort(p_allEqual, new MyComparer<int>());
    }

    [Benchmark]
    public void ArraySort_RandomNear()
    {
        Array.Sort(a_randomNear, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_RandomNear()
    {
        Sort(p_randomNear, new MyComparer<int>());
    }

    [Benchmark]
    public void ArraySort_Random()
    {
        Array.Sort(a_random, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_Random()
    {
        Sort(p_random, new MyComparer<int>());
    }

    [Benchmark]
    public void ArraySort_Sequence()
    {
        Array.Sort(a_sequence, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_Sequence()
    {
        Sort(p_sequence, new MyComparer<int>());
    }

    [Benchmark]
    public void ArraySort_ReverseSequence()
    {
        Array.Sort(a_reverse, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_ReverseSequence()
    {
        Sort(p_reverse, new MyComparer<int>());
    }

    [Benchmark]
    public void ArraySort_Peek()
    {
        Array.Sort(a_peek, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_Peek()
    {
        Sort(p_peek, new MyComparer<int>());
    }

    [Benchmark]
    public void ArraySort_ReversePeek()
    {
        Array.Sort(a_reversePeek, new MyComparer<int>());
    }

    [Benchmark]
    public void PdqSort_ReversePeek()
    {
        Sort(p_reversePeek, new MyComparer<int>());
    }
}

Benchmark result (.NET 7 with PGO+QJFL+OSR enabled):

Method	size	Mean	Error	StdDev	Median	Ratio
ArraySort_AllEqual	10	1,463.4 ns	32.23 ns	58.12 ns	1,500.0 ns	1
PdqSort_AllEqual	10	834.1 ns	20.59 ns	78.67 ns	800.0 ns	0.57
ArraySort_RandomNear	10	1,357.4 ns	33.12 ns	138.41 ns	1,300.0 ns	1
PdqSort_RandomNear	10	933.5 ns	22.61 ns	91.20 ns	900.0 ns	0.69
ArraySort_Random	10	1,465.6 ns	32.81 ns	76.05 ns	1,500.0 ns	1
PdqSort_Random	10	954.5 ns	22.99 ns	67.42 ns	900.0 ns	0.65
ArraySort_Sequence	10	1,279.4 ns	25.42 ns	41.04 ns	1,300.0 ns	1
PdqSort_Sequence	10	829.0 ns	22.52 ns	80.72 ns	800.0 ns	0.65
ArraySort_ReverseSequence	10	1,715.1 ns	38.26 ns	149.87 ns	1,700.0 ns	1
PdqSort_ReverseSequence	10	931.0 ns	24.61 ns	78.48 ns	900.0 ns	0.54
ArraySort_Peek	10	1,458.0 ns	32.85 ns	79.35 ns	1,500.0 ns	1
PdqSort_Peek	10	981.1 ns	23.38 ns	39.71 ns	1,000.0 ns	0.67
ArraySort_ReversePeek	10	1,429.2 ns	32.56 ns	93.94 ns	1,400.0 ns	1
PdqSort_ReversePeek	10	937.8 ns	22.62 ns	78.10 ns	900.0 ns	0.66
ArraySort_AllEqual	100	2,789.1 ns	61.69 ns	131.48 ns	2,800.0 ns	1
PdqSort_AllEqual	100	1,585.6 ns	35.64 ns	111.07 ns	1,600.0 ns	0.57
ArraySort_RandomNear	100	5,160.0 ns	88.53 ns	82.81 ns	5,200.0 ns	1
PdqSort_RandomNear	100	3,783.1 ns	76.42 ns	169.33 ns	3,700.0 ns	0.73
ArraySort_Random	100	5,508.3 ns	101.57 ns	79.30 ns	5,500.0 ns	1
PdqSort_Random	100	4,245.5 ns	88.54 ns	166.29 ns	4,200.0 ns	0.77
ArraySort_Sequence	100	3,443.8 ns	73.83 ns	145.73 ns	3,400.0 ns	1
PdqSort_Sequence	100	1,253.0 ns	29.03 ns	68.43 ns	1,300.0 ns	0.36
ArraySort_ReverseSequence	100	4,566.7 ns	90.67 ns	97.01 ns	4,600.0 ns	1
PdqSort_ReverseSequence	100	1,621.5 ns	35.87 ns	83.84 ns	1,600.0 ns	0.36
ArraySort_Peek	100	6,846.7 ns	139.19 ns	130.20 ns	6,900.0 ns	1
PdqSort_Peek	100	4,163.0 ns	86.57 ns	121.36 ns	4,200.0 ns	0.61
ArraySort_ReversePeek	100	7,307.7 ns	103.27 ns	86.23 ns	7,300.0 ns	1
PdqSort_ReversePeek	100	4,050.0 ns	82.14 ns	94.59 ns	4,000.0 ns	0.55
ArraySort_AllEqual	1000	22,796.2 ns	357.98 ns	298.93 ns	22,850.0 ns	1
PdqSort_AllEqual	1000	2,746.8 ns	59.74 ns	91.23 ns	2,750.0 ns	0.12
ArraySort_RandomNear	1000	60,628.6 ns	829.46 ns	735.30 ns	60,450.0 ns	1
PdqSort_RandomNear	1000	38,600.0 ns	684.45 ns	571.55 ns	38,500.0 ns	0.64
ArraySort_Random	1000	65,485.7 ns	829.97 ns	735.74 ns	65,600.0 ns	1
PdqSort_Random	1000	40,953.3 ns	565.50 ns	528.97 ns	40,800.0 ns	0.63
ArraySort_Sequence	1000	29,757.1 ns	130.62 ns	115.79 ns	29,700.0 ns	1
PdqSort_Sequence	1000	3,255.2 ns	67.21 ns	98.51 ns	3,300.0 ns	0.11
ArraySort_ReverseSequence	1000	47,523.1 ns	827.02 ns	690.60 ns	47,400.0 ns	1
PdqSort_ReverseSequence	1000	4,520.0 ns	92.14 ns	86.19 ns	4,500.0 ns	0.1
ArraySort_Peek	1000	102,807.7 ns	1,237.26 ns	1,033.17 ns	102,800.0 ns	1
PdqSort_Peek	1000	32,327.3 ns	638.66 ns	784.33 ns	32,300.0 ns	0.31
ArraySort_ReversePeek	1000	101,040.0 ns	399.60 ns	373.78 ns	101,200.0 ns	1
PdqSort_ReversePeek	1000	32,715.4 ns	535.21 ns	446.93 ns	32,800.0 ns	0.32
ArraySort_AllEqual	10000	331,531.5 ns	6,628.85 ns	25,170.65 ns	321,700.0 ns	1
PdqSort_AllEqual	10000	17,445.8 ns	339.40 ns	441.32 ns	17,550.0 ns	0.05
ArraySort_RandomNear	10000	796,320.7 ns	15,901.33 ns	44,849.99 ns	782,350.0 ns	1
PdqSort_RandomNear	10000	495,809.5 ns	9,681.32 ns	11,524.93 ns	494,300.0 ns	0.62
ArraySort_Random	10000	802,008.3 ns	10,294.17 ns	8,037.01 ns	798,100.0 ns	1
PdqSort_Random	10000	523,595.2 ns	10,427.60 ns	12,413.32 ns	519,900.0 ns	0.65
ArraySort_Sequence	10000	382,656.2 ns	6,258.24 ns	6,146.43 ns	386,250.0 ns	1
PdqSort_Sequence	10000	22,395.7 ns	442.49 ns	559.61 ns	22,400.0 ns	0.06
ArraySort_ReverseSequence	10000	671,491.3 ns	12,820.65 ns	16,214.02 ns	672,900.0 ns	1
PdqSort_ReverseSequence	10000	32,521.1 ns	654.01 ns	726.93 ns	32,700.0 ns	0.05
ArraySort_Peek	10000	1,653,403.6 ns	32,723.50 ns	69,736.44 ns	1,627,400.0 ns	1
PdqSort_Peek	10000	332,523.5 ns	5,159.49 ns	5,298.41 ns	334,300.0 ns	0.2
ArraySort_ReversePeek	10000	1,550,048.3 ns	29,011.67 ns	42,524.93 ns	1,534,900.0 ns	1
PdqSort_ReversePeek	10000	334,310.3 ns	6,278.59 ns	9,203.08 ns	332,300.0 ns	0.22
ArraySort_AllEqual	100000	3,829.3 us	71.13 us	55.54 us	3,830.1 us	1
PdqSort_AllEqual	100000	302.7 us	5.87 us	15.47 us	297.7 us	0.08
ArraySort_RandomNear	100000	9,242.4 us	135.47 us	126.71 us	9,264.8 us	1
PdqSort_RandomNear	100000	6,155.5 us	79.26 us	70.26 us	6,160.2 us	0.67
ArraySort_Random	100000	10,288.1 us	125.94 us	105.16 us	10,306.8 us	1
PdqSort_Random	100000	6,454.4 us	121.92 us	140.41 us	6,423.8 us	0.63
ArraySort_Sequence	100000	5,080.0 us	94.07 us	83.39 us	5,072.1 us	1
PdqSort_Sequence	100000	421.7 us	5.25 us	4.66 us	422.9 us	0.08
ArraySort_ReverseSequence	100000	9,445.3 us	136.01 us	127.22 us	9,454.7 us	1
PdqSort_ReverseSequence	100000	323.9 us	6.12 us	19.18 us	311.6 us	0.03
ArraySort_Peek	100000	21,027.5 us	410.74 us	384.21 us	21,061.0 us	1
PdqSort_Peek	100000	3,614.3 us	70.26 us	91.36 us	3,590.5 us	0.17
ArraySort_ReversePeek	100000	21,216.7 us	194.14 us	181.60 us	21,215.7 us	1
PdqSort_ReversePeek	100000	3,690.6 us	55.66 us	46.48 us	3,681.0 us	0.17
ArraySort_AllEqual	1000000	48,913.4 us	286.55 us	223.72 us	48,967.5 us	1
PdqSort_AllEqual	1000000	5,175.4 us	103.50 us	1,085.55 us	5,314.0 us	0.11
ArraySort_RandomNear	1000000	112,398.0 us	848.60 us	708.62 us	112,358.6 us	1
PdqSort_RandomNear	1000000	74,713.3 us	1,222.39 us	1,143.43 us	74,416.4 us	0.66
ArraySort_Random	1000000	116,767.4 us	1,071.41 us	1,002.20 us	116,511.4 us	1
PdqSort_Random	1000000	77,163.1 us	541.12 us	451.86 us	77,059.6 us	0.66
ArraySort_Sequence	1000000	66,112.9 us	1,227.28 us	1,147.99 us	65,879.6 us	1
PdqSort_Sequence	1000000	5,845.8 us	116.89 us	1,016.63 us	6,014.9 us	0.09
ArraySort_ReverseSequence	1000000	105,905.3 us	1,072.63 us	1,003.34 us	105,948.4 us	1
PdqSort_ReverseSequence	1000000	7,452.4 us	149.00 us	1,133.04 us	7,546.2 us	0.07
ArraySort_Peek	1000000	262,358.3 us	1,217.47 us	1,079.26 us	262,020.5 us	1
PdqSort_Peek	1000000	42,478.6 us	657.92 us	549.40 us	42,695.4 us	0.16
ArraySort_ReversePeek	1000000	261,885.1 us	1,831.46 us	1,623.54 us	262,027.0 us	1
PdqSort_ReversePeek	1000000	42,101.3 us	499.68 us	390.11 us	42,174.1 us	0.16