Sorting Algorithms example in C#

SortBenchmark.cs

// BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.1098/21H2)
// 11th Gen Intel Core i5-11400F 2.60GHz, 1 CPU, 12 logical and 6 physical cores
// .NET SDK=6.0.402
//   [Host]     : .NET 6.0.10 (6.0.1022.47605), X64 RyuJIT AVX2
//   DefaultJob : .NET 6.0.10 (6.0.1022.47605), X64 RyuJIT AVX2
//
//
// |        Method |       Mean |    Error |   StdDev | Ratio | RatioSD |   Gen0 | Allocated | Alloc Ratio |
// |-------------- |-----------:|---------:|---------:|------:|--------:|-------:|----------:|------------:|
// | InsertionSort |   131.3 ns |  0.43 ns |  0.36 ns |  0.29 |    0.00 |      - |         - |        0.00 |
// |    BufferSort |   360.3 ns |  2.76 ns |  2.58 ns |  0.80 |    0.01 | 0.1349 |     848 B |        1.15 |
// |     QuickSort |   428.6 ns |  4.59 ns |  4.29 ns |  0.96 |    0.01 |      - |         - |        0.00 |
// |      LinqSort |   448.0 ns |  1.66 ns |  1.55 ns |  1.00 |    0.00 | 0.1173 |     736 B |        1.00 |
// |     MergeSort |   787.2 ns | 14.66 ns | 13.71 ns |  1.76 |    0.03 | 0.3042 |    1912 B |        2.60 |
// |    SimpleSort |   893.1 ns |  1.95 ns |  1.83 ns |  1.99 |    0.01 |      - |         - |        0.00 |
// | SelectionSort |   914.3 ns |  5.40 ns |  4.78 ns |  2.04 |    0.01 |      - |         - |        0.00 |
// |    BubbleSort | 1,044.9 ns |  3.18 ns |  2.97 ns |  2.33 |    0.01 |      - |         - |        0.00 |

// Explanations => https://www.youtube.com/watch?v=l7-f9gS8VOs
// the time complexity for all except the MergeSort is O(n) and the merge sort is O(nlog(n))

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Order;

namespace ConsoleApp1;

[MemoryDiagnoser()]
[Orderer(SummaryOrderPolicy.FastestToSlowest)]
public class SortBenchmark
{
    public IList<PriorityItem> List  = default!;

    [GlobalSetup]
    public void init()
    {
        List = new List<PriorityItem>
        {
            new() { Priority = Priority.Medium },
            new() { Priority = Priority.High },
            new() { Priority = Priority.Low },
            new() { Priority = Priority.High },
            new() { Priority = Priority.Medium },
            new() { Priority = Priority.Low },
            new() { Priority = Priority.High },
            new() { Priority = Priority.Medium },
            new() { Priority = Priority.Medium },
            new() { Priority = Priority.Medium },
            new() { Priority = Priority.High },
            new() { Priority = Priority.Low },
            new() { Priority = Priority.Low },
            new() { Priority = Priority.Low },
            new() { Priority = Priority.High },
            new() { Priority = Priority.Low },
            new() { Priority = Priority.Medium },
            new() { Priority = Priority.High },
        };
    }

    [Benchmark(Baseline = true)]
    public void LinqSort()
    {
        var _ = List.OrderBy(q => q.Priority).ToList();
    }

    [Benchmark()]
    public void SimpleSort() => SimpleSort(List);
    
    
    [Benchmark()]
    public void InsertionSort() => InsertionSort(List,List.Count);
    

    [Benchmark()]
    public void BubbleSort() => BubbleSort(List,List.Count);
    
    
    [Benchmark()]
    public void BufferSort() => BufferSort(ref List);
    
    
    [Benchmark()]
    public void MergeSort() => MergeSort(List,List.Count);
    
    [Benchmark()]
    public void SelectionSort() => SelectionSort(List,List.Count);
    
    
    [Benchmark()]
    public void QuickSort() => QuickSort(List);

    #region "Quick Sort"

    void QuickSort(IList<PriorityItem> list)
    {
        QSort(list , 0, list.Count);
    }

    void QSort(IList<PriorityItem> list, int left, int right)
    {
        int i = left - 1,
            j = right;

        while (true)
        {
            var d = list[left].Priority;
            do i++; while (list[i].Priority < d);
            do j--; while (list[j].Priority > d);

            if (i < j)
            {
                (list[i], list[j]) = (list[j], list[i]);
            }
            else
            {
                if (left < j) QSort(list, left, j);
                if (++j < right) QSort(list, j, right);
                return;
            }
        }
    }
    #endregion
    
    #region "Buffer Sort"

    void BufferSort(ref IList<PriorityItem> list)
    {
        var lowBuffer = new List<PriorityItem>();
        var midBuffer = new List<PriorityItem>();
        var HighBuffer = new List<PriorityItem>();

        for (int i = 0; i < list.Count; i++)
        {
            if (list[i].Priority == Priority.Low)
                lowBuffer.Add(list[i]);

            else if (list[i].Priority == Priority.Medium)
                midBuffer.Add(list[i]);

            else if (list[i].Priority == Priority.High)
                HighBuffer.Add(list[i]);
        }

        list = lowBuffer.Concat(midBuffer).Concat(HighBuffer).ToList();
    }

    #endregion

    #region "Merge Sort"

    void MergeSort(IList<PriorityItem> list, int n)
    {
        MrgSort(list, 0, n - 1);
    }

// auxiliary function (helper function)
    void MrgSort(IList<PriorityItem> list, int start, int end)
    {
        if (start >= end) return;
        var m = (start + end) / 2;
        MrgSort(list, start, m);
        MrgSort(list, m + 1, end);
        Combine(list, start, m, end);
    }

    void Combine(IList<PriorityItem> list, int start, int m, int end)
    {
        var buffer = new PriorityItem[end + 1];
        var k = start;
        while (k <= end)
        {
            buffer[k] = list[k];
            k = k + 1;
        }

        var i = start;
        var j = m + 1;
        k = start;

        while (i <= m && j <= end)
        {
            if (buffer[i].Priority <= buffer[j].Priority)
            {
                list[k] = buffer[i];
                i++;
            }
            else
            {
                list[k] = buffer[j];
                j++;
            }

            k++;
        }

        while (i <= m)
        {
            list[k] = buffer[i];
            i++;
            k++;
        }

        while (j <= end)
        {
            list[k] = buffer[j];
            j++;
            k++;
        }
    }

    #endregion

    #region "Insertion Sort"

    void InsertionSort(IList<PriorityItem> list, int n)
    {
        var i = 1;
        while (i < n)
        {
            InsertIth(list, n, i);
            i++;
        }
    }

    void InsertIth(IList<PriorityItem> list, int n, int i)
    {
        var key = list[i];
        var j = i - 1;
        while (j >= 0 && list[j].Priority > key.Priority)
        {
            list[j + 1] = list[j];
            j = j - 1;
        }

        list[j + 1] = key;
    }

    #endregion

    #region "Bubble Sort"

    void Bubble(IList<PriorityItem> list, int n)
    {
        var i = n - 1;
        while (i > 0)
        {
            if (list[i].Priority < list[i - 1].Priority)
            {
                (list[i], list[i - 1]) = (list[i - 1], list[i]);
            }

            i--;
        }
    }

    void BubbleSort(IList<PriorityItem> list, int n)
    {
        var i = 0;
        while (i < n - 1)
        {
            Bubble(list, n);
            i++;
        }
    }

    #endregion

    #region "Simple Sort"

    void SimpleSort(IList<PriorityItem> list)
    {
        for (int i = 0; i < list.Count; i++)
        {
            for (int j = i + 1; j < list.Count; j++)
            {
                if (list[i].Priority > list[j].Priority)
                {
                    (list[i], list[j]) = (list[j], list[i]);
                    continue;
                }
            }
        }
    }

    #endregion

    #region "Selection Sort"

    int LocationOfSmallest(IList<PriorityItem> list, int start, int end)
    {
        int i = start;
        int j = i;
        while (i <= end)
        {
            if (list[i].Priority < list[j].Priority)
            {
                j = i;
            }

            i = i + 1;
        }

        return j;
    }

    void SelectionSort(IList<PriorityItem> list, int n)
    {
        int i = 0;
        while (i < n - 1)
        {
            int j = LocationOfSmallest(list, i, n - 1);
            (list[i], list[j]) = (list[j], list[i]); // swap
            i++;
        }
    }

    #endregion

    public enum Priority
    {
        High,
        Medium,
        Low
    }

    public class PriorityItem
    {
        public Priority Priority { get; set; }
    }
}