Sorting.cs

using System;
using System.Collections.Generic;

static class Bubble
{
    internal static void Sort(int[] value)
    {
        int[] collection = new int[value.Length];
        value.CopyTo(collection, default);

        // Iterate the array.
        for (int i = default; i < collection.Length; i++)
        {

            // Restrict unsorted elements to the left.
            for (int j = default; j < collection.Length - i - 1; j++)
            {
                // Inspect if the adjacent elements need to be swapped or not.
                if (collection[j + 1] < collection[j])
                    (collection[j + 1], collection[j]) = (collection[j], collection[j + 1]);
            }
        }

    }
}

static class Selection
{
    internal static void Sort(int[] value)
    {
        int[] collection = new int[value.Length];
        value.CopyTo(collection, default);

        Console.WriteLine("Selection Sort:");
        Console.WriteLine($"0 ~ [{string.Join(", ", collection)}]");

        // Iterate the array.
        for (int i = default; i < collection.Length; i++)
        {
            // Cache the current index.
            var index = i;

            // Restrict unsorted elements to the right.
            // Inspect & find the smallest value & cache its index.
            for (int j = i + 1; j < collection.Length; j++)
                if (collection[j] < collection[index]) index = j;

            // Swap elements.
            (collection[i], collection[index]) = (collection[index], collection[i]);
        }

        Console.WriteLine();
    }
}

static class Insertion
{
    internal static void Sort(int[] value)
    {
        int[] collection = new int[value.Length];
        value.CopyTo(collection, default);

        // Iterate the array.
        for (int i = default; i < collection.Length; i++)
        {
            // Cache the value at the current index.
            var key = collection[i];

            // Cache the length of the sorted segment. 
            int j = i - 1;

            // Attempt to shift unsorted elements to the right.
            for (; j >= 0 && collection[j] > key; --j)
                collection[j + 1] = collection[j];

            // Insert the sorted element.
            collection[j + 1] = key;
        }
    }
}

static class Merge
{
    internal static void Sort(int[] value)
    {
        int[] collection = new int[value.Length];
        value.CopyTo(collection, default);

        Console.WriteLine($"[{string.Join(", ", collection)}]");

        // Specify the range of elements, typically 0 ~ collection length.
        Sort(ref collection, default, collection.Length - 1);

        Console.WriteLine($"[{string.Join(", ", collection)}]");
    }

    static void Sort(ref int[] collection, int low, int high)
    {
        // Check if the start is greater than the end, if it is then don't do anything.
        if (low >= high) return;

        // Attempt to get the middle index so we may split the array.
        int middle = (low + high) / 2;

        // Perform sorting on the left part of the array.
        Sort(ref collection, low, middle);

        // Perform sorting on the right part of the array.
        Sort(ref collection, middle + 1, high);

        // Combine the arrays back into a single array.
        Combine(ref collection, low, middle, high);
    }

    static void Combine(ref int[] collection, int low, int middle, int high)
    {
        // Store our result in a list.
        List<int> list = [];

        // Define ranges for each left & right of the array.
        int left = low, right = middle + 1;

        // Keep looping until either left or right parts exceed their limit.

        while (left <= middle && right <= high)

            // Check if the element on the left is smaller than the element on the right.
            // Accordingly decide where to push to.

            if (collection[left] <= collection[right])
                list.Add(collection[left++]);
            else
                list.Add(collection[right++]);

        // Push any remaining elements into the left array.
        while (left <= middle)
            list.Add(collection[left++]);

        // Push any remaining elements into the right array.
        while (right <= high)
            list.Add(collection[right++]);

        // Merge & copy the data back to the original array.
        for (int i = low; i <= high; i++)
            collection[i] = list[i - low];
    }
}

static class Quick
{
    internal static void Sort(int[] value)
    {
        int[] collection = new int[value.Length];

        value.CopyTo(collection, default);
        Console.WriteLine($"[{string.Join(", ", collection)}]");
        Sort(collection, default, collection.Length - 1);
        Console.WriteLine($"[{string.Join(", ", collection)}]");
    }

    static void Sort(int[] collection, int left, int right)
    {
        // Check if the start excceds the end, if it does simply return.
        if (left >= right) return;

        // Obtain the pivot from partitoning the array.
        int pivot = Part(collection, left, right);

        // Sort the left part.
        Sort(collection, left, pivot - 1);

        // Sort the right part.
        Sort(collection, pivot + 1, right);
    }

    static int Part(int[] collection, int left, int right)
    {
        // Assume the pivot is the last element in the subarray.
        int pivot = collection[right];

        // Cache the index from where smaller elements should be placed.
        int i = left - 1;

        // Shift smaller elements to the left.
        for (int j = left; j < right; j++)
            if (collection[j] < pivot)
            {
                i += 1;
                (collection[j], collection[i]) = (collection[i], collection[j]);
            }

        // Ensure the pivot is in the correct position.
        (collection[right], collection[i + 1]) = (collection[i + 1], collection[right]);

        // Return the index of the pivot.
        return i + 1;
    }
}

static class Program
{
    static void Main()
    {
        int[] collection = [12, 35, 27, 10, 38, 18, 45, 48];

        Quick.Sort(collection);
        // Bubble.Sort(collection);
        //   Selection.Sort(collection);
        //   Insertion.Sort(collection);
    }
}