BinaryInsertionSorter.cs

using System;
using System.Collections.Generic;

namespace Algorithms.Sorters.Comparison;

/// <summary>
///     TODO.
/// </summary>
/// <typeparam name="T">TODO. 2.</typeparam>
public class BinaryInsertionSorter<T> : IComparisonSorter<T>
{
    /// <summary>
    ///     Sorts array using specified comparer,
    ///     variant of insertion sort where binary search is used to find place for next element
    ///     internal, in-place, unstable,
    ///     time complexity: O(n^2),
    ///     space complexity: O(1),
    ///     where n - array length.
    /// </summary>
    /// <param name="array">Array to sort.</param>
    /// <param name="comparer">Compares elements.</param>
    public void Sort(T[] array, IComparer<T> comparer)
    {
        for (var i = 1; i < array.Length; i++)
        {
            var target = array[i];
            var moveIndex = i - 1;
            var targetInsertLocation = BinarySearch(array, 0, moveIndex, target, comparer);
            Array.Copy(array, targetInsertLocation, array, targetInsertLocation + 1, i - targetInsertLocation);

            array[targetInsertLocation] = target;
        }
    }

    /// <summary>Implementation of Binary Search using an iterative approach.</summary>
    /// <param name="array">
    ///     An array of values sorted in ascending order between the index values left and right to search
    ///     through.
    /// </param>
    /// <param name="from">Left index to search from (inclusive).</param>
    /// <param name="to">Right index to search to (inclusive).</param>
    /// <param name="target">The value to find placefor in the provided array.</param>
    /// <param name="comparer">TODO.</param>
    /// <returns>The index where to insert target value.</returns>
    private static int BinarySearch(T[] array, int from, int to, T target, IComparer<T> comparer)
    {
        var left = from;
        var right = to;
        while (right > left)
        {
            var middle = (left + right) / 2;
            var comparisonResult = comparer.Compare(target, array[middle]);

            if (comparisonResult == 0)
            {
                return middle + 1;
            }

            if (comparisonResult > 0)
            {
                left = middle + 1;
            }
            else
            {
                right = middle - 1;
            }
        }

        return comparer.Compare(target, array[left]) < 0 ? left : left + 1;
    }
}