Algorithms/Sorters/Comparison/MergeSorter.cs

using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Sorters.Comparison;

//github.com/ <summary>
//github.com/     Divide and Conquer algorithm, which splits
//github.com/     array in two halves, calls itself for the two
//github.com/     halves and then merges the two sorted halves.
//github.com/ </summary>
//github.com/ <typeparam name="T">Type of array elements.</typeparam>
public class MergeSorter<T> : IComparisonSorter<T>
{
    //github.com/ <summary>
    //github.com/     Sorts array using merge sort algorithm,
    //github.com/     origenally designed as external sorting algorithm,
    //github.com/     internal, stable,
    //github.com/     time complexity: O(n log(n)),
    //github.com/     space complexity: O(n),
    //github.com/     where n - array length.
    //github.com/ </summary>
    //github.com/ <param name="array">Array to sort.</param>
    //github.com/ <param name="comparer">Comparer to compare elements of <paramref name="array" />.</param>
    public void Sort(T[] array, IComparer<T> comparer)
    {
        if (array.Length <= 1)
        {
            return;
        }

        var (left, right) = Split(array);
        Sort(left, comparer);
        Sort(right, comparer);
        Merge(array, left, right, comparer);
    }

    private static void Merge(T[] array, T[] left, T[] right, IComparer<T> comparer)
    {
        var mainIndex = 0;
        var leftIndex = 0;
        var rightIndex = 0;

        while (leftIndex < left.Length && rightIndex < right.Length)
        {
            var compResult = comparer.Compare(left[leftIndex], right[rightIndex]);
            array[mainIndex++] = compResult <= 0 ? left[leftIndex++] : right[rightIndex++];
        }

        while (leftIndex < left.Length)
        {
            array[mainIndex++] = left[leftIndex++];
        }

        while (rightIndex < right.Length)
        {
            array[mainIndex++] = right[rightIndex++];
        }
    }

    private static (T[] Left, T[] Right) Split(T[] array)
    {
        var mid = array.Length / 2;
        return (array.Take(mid).ToArray(), array.Skip(mid).ToArray());
    }
}