TimSorter.cs

using System;
using System.Collections.Generic;

namespace Algorithms.Sorters.Comparison;

/// <summary>
///     Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.
///     It was originally implemented by Tim Peters in 2002 for use in the Python programming language.
///
///     This class is based on a Java interpretation of Tim Peter's original work.
///     Java class is viewable here:
///     http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
///
///     Tim Peters's list sort for Python, is described in detail here:
///     http://svn.python.org/projects/python/trunk/Objects/listsort.txt
///
///     Tim's C code may be found here: http://svn.python.org/projects/python/trunk/Objects/listobject.c
///
///     The underlying techniques are described in this paper (and may have even earlier origins):
///     "Optimistic Sorting and Information Theoretic Complexity"
///     Peter McIlroy
///     SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
///     pp 467-474, Austin, Texas, 25-27 January 1993.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class TimSorter<T> : IComparisonSorter<T>
{
    private readonly int minMerge;
    private readonly int initMinGallop;
    private readonly int[] runBase;
    private readonly int[] runLengths;

    private int minGallop;
    private int stackSize;

    private IComparer<T> comparer = default!;

    /// <summary>
    /// Private class for handling gallop merges, allows for tracking array indexes and wins.
    /// </summary>
    /// <typeparam name="Tc">Type of array element.</typeparam>
    private class TimChunk<Tc>
    {
        public Tc[] Array { get; set; } = default!;

        public int Index { get; set; }

        public int Remaining { get; set; }

        public int Wins { get; set; }
    }

    public TimSorter(int minMerge = 32, int minGallop = 7)
    {
        initMinGallop = minGallop;
        this.minMerge = minMerge;
        runBase = new int[85];
        runLengths = new int[85];

        stackSize = 0;
        this.minGallop = minGallop;
    }

    /// <summary>
    ///     Sorts array using specified comparer
    ///     worst case performance: O(n log(n)),
    ///     best case performance:  O(n),
    ///     See <a href="https://en.wikipedia.org/wiki/Timsort">here</a> for more info.
    /// </summary>
    /// <param name="array">Array to sort.</param>
    /// <param name="comparer">Compares elements.</param>
    public void Sort(T[] array, IComparer<T> comparer)
    {
        this.comparer = comparer;
        var start = 0;
        var remaining = array.Length;

        if (remaining < minMerge)
        {
            if (remaining < 2)
            {
                // Arrays of size 0 or 1 are always sorted.
                return;
            }

            // Don't need to merge, just binary sort
            BinarySort(array, start, remaining, start);
            return;
        }

        var minRun = MinRunLength(remaining, minMerge);

        do
        {
            // Identify next run
            var runLen = CountRunAndMakeAscending(array, start);

            // If the run is too short extend to Min(MIN_RUN, remaining)
            if (runLen < minRun)
            {
                var force = Math.Min(minRun, remaining);
                BinarySort(array, start, start + force, start + runLen);
                runLen = force;
            }

            runBase[stackSize] = start;
            runLengths[stackSize] = runLen;
            stackSize++;

            MergeCollapse(array);

            start += runLen;
            remaining -= runLen;
        }
        while (remaining != 0);

        MergeForceCollapse(array);
    }

    /// <summary>
    /// Returns the minimum acceptable run length for an array of the specified
    /// length.Natural runs shorter than this will be extended.
    ///
    /// Computation is:
    ///   If total less than minRun, return n (it's too small to bother with fancy stuff).
    ///   Else if total is an exact power of 2, return minRun/2.
    ///   Else return an int k, where <![CDATA[minRun/2 <= k <= minRun]]>, such that total/k
    ///     is close to, but strictly less than, an exact power of 2.
    /// </summary>
    /// <param name="total">Total length remaining to sort.</param>
    /// <returns>Minimum run length to be merged.</returns>
    private static int MinRunLength(int total, int minRun)
    {
        var r = 0;
        while (total >= minRun)
        {
            r |= total & 1;
            total >>= 1;
        }

        return total + r;
    }

    /// <summary>
    /// Reverse the specified range of the specified array.
    /// </summary>
    /// <param name="array">the array in which a range is to be reversed.</param>
    /// <param name="start">the index of the first element in the range to be reversed.</param>
    /// <param name="end">the index after the last element in the range to be reversed.</param>
    private static void ReverseRange(T[] array, int start, int end)
    {
        end--;
        while (start < end)
        {
            var t = array[start];
            array[start++] = array[end];
            array[end--] = t;
        }
    }

    /// <summary>
    /// Left shift a value, preventing a roll over to negative numbers.
    /// </summary>
    /// <param name="shiftable">int value to left shift.</param>
    /// <returns>Left shifted value, bound to 2,147,483,647.</returns>
    private static int BoundLeftShift(int shiftable) => (shiftable << 1) < 0
            ? (shiftable << 1) + 1
            : int.MaxValue;

    /// <summary>
    /// Check the chunks before getting in to a merge to make sure there's something to actually do.
    /// </summary>
    /// <param name="left">TimChunk of the left hand side.</param>
    /// <param name="right">TimChunk of the right hand side.</param>
    /// <param name="dest">The current target point for the remaining values.</param>
    /// <returns>If a merge is required.</returns>
    private static bool NeedsMerge(TimChunk<T> left, TimChunk<T> right, ref int dest)
    {
        right.Array[dest++] = right.Array[right.Index++];
        if (--right.Remaining == 0)
        {
            Array.Copy(left.Array, left.Index, right.Array, dest, left.Remaining);
            return false;
        }

        if (left.Remaining == 1)
        {
            Array.Copy(right.Array, right.Index, right.Array, dest, right.Remaining);
            right.Array[dest + right.Remaining] = left.Array[left.Index];
            return false;
        }

        return true;
    }

    /// <summary>
    /// Moves over the last parts of the chunks.
    /// </summary>
    /// <param name="left">TimChunk of the left hand side.</param>
    /// <param name="right">TimChunk of the right hand side.</param>
    /// <param name="dest">The current target point for the remaining values.</param>
    private static void FinalizeMerge(TimChunk<T> left, TimChunk<T> right, int dest)
    {
        if (left.Remaining == 1)
        {
            Array.Copy(right.Array, right.Index, right.Array, dest, right.Remaining);
            right.Array[dest + right.Remaining] = left.Array[left.Index];
        }
        else if (left.Remaining == 0)
        {
            throw new ArgumentException("Comparison method violates its general contract!");
        }
        else
        {
            Array.Copy(left.Array, left.Index, right.Array, dest, left.Remaining);
        }
    }

    /// <summary>
    /// Returns the length of the run beginning at the specified position in
    /// the specified array and reverses the run if it is descending (ensuring
    /// that the run will always be ascending when the method returns).
    ///
    /// A run is the longest ascending sequence with:
    ///
    ///    <![CDATA[a[lo] <= a[lo + 1] <= a[lo + 2] <= ...]]>
    ///
    /// or the longest descending sequence with:
    ///
    ///    <![CDATA[a[lo] >  a[lo + 1] >  a[lo + 2] >  ...]]>
    ///
    /// For its intended use in a stable mergesort, the strictness of the
    /// definition of "descending" is needed so that the call can safely
    /// reverse a descending sequence without violating stability.
    /// </summary>
    /// <param name="array">the array in which a run is to be counted and possibly reversed.</param>
    /// <param name="start">index of the first element in the run.</param>
    /// <returns>the length of the run beginning at the specified position in the specified array.</returns>
    private int CountRunAndMakeAscending(T[] array, int start)
    {
        var runHi = start + 1;
        if (runHi == array.Length)
        {
            return 1;
        }

        // Find end of run, and reverse range if descending
        if (comparer.Compare(array[runHi++], array[start]) < 0)
        { // Descending
            while (runHi < array.Length && comparer.Compare(array[runHi], array[runHi - 1]) < 0)
            {
                runHi++;
            }

            ReverseRange(array, start, runHi);
        }
        else
        { // Ascending
            while (runHi < array.Length && comparer.Compare(array[runHi], array[runHi - 1]) >= 0)
            {
                runHi++;
            }
        }

        return runHi - start;
    }

    /// <summary>
    /// Find the position in the array that a key should fit to the left of where it currently sits.
    /// </summary>
    /// <param name="array">Array to search.</param>
    /// <param name="key">Key to place in the array.</param>
    /// <param name="i">Base index for the key.</param>
    /// <param name="len">Length of the chunk to run through.</param>
    /// <param name="hint">Initial starting position to start from.</param>
    /// <returns>Offset for the key's location.</returns>
    private int GallopLeft(T[] array, T key, int i, int len, int hint)
    {
        var (offset, lastOfs) = comparer.Compare(key, array[i + hint]) > 0
            ? RightRun(array, key, i, len, hint, 0)
            : LeftRun(array, key, i, hint, 1);

        return FinalOffset(array, key, i, offset, lastOfs, 1);
    }

    /// <summary>
    /// Find the position in the array that a key should fit to the right of where it currently sits.
    /// </summary>
    /// <param name="array">Array to search.</param>
    /// <param name="key">Key to place in the array.</param>
    /// <param name="i">Base index for the key.</param>
    /// <param name="len">Length of the chunk to run through.</param>
    /// <param name="hint">Initial starting position to start from.</param>
    /// <returns>Offset for the key's location.</returns>
    private int GallopRight(T[] array, T key, int i, int len, int hint)
    {
        var (offset, lastOfs) = comparer.Compare(key, array[i + hint]) < 0
            ? LeftRun(array, key, i, hint, 0)
            : RightRun(array, key, i, len, hint, -1);

        return FinalOffset(array, key, i, offset, lastOfs, 0);
    }

    private (int offset, int lastOfs) LeftRun(T[] array, T key, int i, int hint, int lt)
    {
        var maxOfs = hint + 1;
        var (offset, tmp) = (1, 0);

        while (offset < maxOfs && comparer.Compare(key, array[i + hint - offset]) < lt)
        {
            tmp = offset;
            offset = BoundLeftShift(offset);
        }

        if (offset > maxOfs)
        {
            offset = maxOfs;
        }

        var lastOfs = hint - offset;
        offset = hint - tmp;

        return (offset, lastOfs);
    }

    private (int offset, int lastOfs) RightRun(T[] array, T key, int i, int len, int hint, int gt)
    {
        var (offset, lastOfs) = (1, 0);
        var maxOfs = len - hint;
        while (offset < maxOfs && comparer.Compare(key, array[i + hint + offset]) > gt)
        {
            lastOfs = offset;
            offset = BoundLeftShift(offset);
        }

        if (offset > maxOfs)
        {
            offset = maxOfs;
        }

        offset += hint;
        lastOfs += hint;

        return (offset, lastOfs);
    }

    private int FinalOffset(T[] array, T key, int i, int offset, int lastOfs, int lt)
    {
        lastOfs++;
        while (lastOfs < offset)
        {
            var m = lastOfs + (int)((uint)(offset - lastOfs) >> 1);

            if (comparer.Compare(key, array[i + m]) < lt)
            {
                offset = m;
            }
            else
            {
                lastOfs = m + 1;
            }
        }

        return offset;
    }

    /// <summary>
    /// Sorts the specified portion of the specified array using a binary
    /// insertion sort. It requires O(n log n) compares, but O(n^2) data movement.
    /// </summary>
    /// <param name="array">Array to sort.</param>
    /// <param name="start">The index of the first element in the range to be sorted.</param>
    /// <param name="end">The index after the last element in the range to be sorted.</param>
    /// <param name="first">The index of the first element in the range that is not already known to be sorted, must be between start and end.</param>
    private void BinarySort(T[] array, int start, int end, int first)
    {
        if (first >= end || first <= start)
        {
            first = start + 1;
        }

        for (; first < end; first++)
        {
            var target = array[first];
            var targetInsertLocation = BinarySearch(array, start, first - 1, target);
            Array.Copy(array, targetInsertLocation, array, targetInsertLocation + 1, first - targetInsertLocation);

            array[targetInsertLocation] = target;
        }
    }

    private int BinarySearch(T[] array, int left, int right, T target)
    {
        while (left < right)
        {
            var mid = (left + right) >> 1;
            if (comparer.Compare(target, array[mid]) < 0)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

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

    private void MergeCollapse(T[] array)
    {
        while (stackSize > 1)
        {
            var n = stackSize - 2;
            if (n > 0 && runLengths[n - 1] <= runLengths[n] + runLengths[n + 1])
            {
                if (runLengths[n - 1] < runLengths[n + 1])
                {
                    n--;
                }

                MergeAt(array, n);
            }
            else if (runLengths[n] <= runLengths[n + 1])
            {
                MergeAt(array, n);
            }
            else
            {
                break;
            }
        }
    }

    private void MergeForceCollapse(T[] array)
    {
        while (stackSize > 1)
        {
            var n = stackSize - 2;
            if (n > 0 && runLengths[n - 1] < runLengths[n + 1])
            {
                n--;
            }

            MergeAt(array, n);
        }
    }

    private void MergeAt(T[] array, int index)
    {
        var baseA = runBase[index];
        var lenA = runLengths[index];
        var baseB = runBase[index + 1];
        var lenB = runLengths[index + 1];

        runLengths[index] = lenA + lenB;

        if (index == stackSize - 3)
        {
            runBase[index + 1] = runBase[index + 2];
            runLengths[index + 1] = runLengths[index + 2];
        }

        stackSize--;

        var k = GallopRight(array, array[baseB], baseA, lenA, 0);

        baseA += k;
        lenA -= k;

        if (lenA <= 0)
        {
            return;
        }

        lenB = GallopLeft(array, array[baseA + lenA - 1], baseB, lenB, lenB - 1);

        if (lenB <= 0)
        {
            return;
        }

        Merge(array, baseA, lenA, baseB, lenB);
    }

    private void Merge(T[] array, int baseA, int lenA, int baseB, int lenB)
    {
        var endA = baseA + lenA;
        var dest = baseA;

        TimChunk<T> left = new()
        {
            Array = array[baseA..endA],
            Remaining = lenA,
        };

        TimChunk<T> right = new()
        {
            Array = array,
            Index = baseB,
            Remaining = lenB,
        };

        // Move first element of the right chunk and deal with degenerate cases.
        if (!TimSorter<T>.NeedsMerge(left, right, ref dest))
        {
            // One of the chunks had 0-1 items in it, so no need to merge anything.
            return;
        }

        var gallop = minGallop;

        while (RunMerge(left, right, ref dest, ref gallop))
        {
            // Penalize for leaving gallop mode
            gallop = gallop > 0
                ? gallop + 2
                : 2;
        }

        minGallop = gallop >= 1
            ? gallop
            : 1;

        FinalizeMerge(left, right, dest);
    }

    private bool RunMerge(TimChunk<T> left, TimChunk<T> right, ref int dest, ref int gallop)
    {
        // Reset the number of times in row a run wins.
        left.Wins = 0;
        right.Wins = 0;

        // Run a stable merge sort until (if ever) one run starts winning consistently.
        if (StableMerge(left, right, ref dest, gallop))
        {
            // Stable merge sort completed with no viable gallops, time to exit.
            return false;
        }

        // One run is winning so consistently that galloping may be a huge win.
        // So try that, and continue galloping until (if ever) neither run appears to be winning consistently anymore.
        do
        {
            if (GallopMerge(left, right, ref dest))
            {
                // Galloped all the way to the end, merge is complete.
                return false;
            }

            // We had a bit of a run, so make it easier to get started again.
            gallop--;
        }
        while (left.Wins >= initMinGallop || right.Wins >= initMinGallop);

        return true;
    }

    private bool StableMerge(TimChunk<T> left, TimChunk<T> right, ref int dest, int gallop)
    {
        do
        {
            if (comparer.Compare(right.Array[right.Index], left.Array[left.Index]) < 0)
            {
                right.Array[dest++] = right.Array[right.Index++];
                right.Wins++;
                left.Wins = 0;
                if (--right.Remaining == 0)
                {
                    return true;
                }
            }
            else
            {
                right.Array[dest++] = left.Array[left.Index++];
                left.Wins++;
                right.Wins = 0;
                if (--left.Remaining == 1)
                {
                    return true;
                }
            }
        }
        while ((left.Wins | right.Wins) < gallop);

        return false;
    }

    private bool GallopMerge(TimChunk<T> left, TimChunk<T> right, ref int dest)
    {
        left.Wins = GallopRight(left.Array, right.Array[right.Index], left.Index, left.Remaining, 0);
        if (left.Wins != 0)
        {
            Array.Copy(left.Array, left.Index, right.Array, dest, left.Wins);
            dest += left.Wins;
            left.Index += left.Wins;
            left.Remaining -= left.Wins;
            if (left.Remaining <= 1)
            {
                return true;
            }
        }

        right.Array[dest++] = right.Array[right.Index++];
        if (--right.Remaining == 0)
        {
            return true;
        }

        right.Wins = GallopLeft(right.Array, left.Array[left.Index], right.Index, right.Remaining, 0);
        if (right.Wins != 0)
        {
            Array.Copy(right.Array, right.Index, right.Array, dest, right.Wins);
            dest += right.Wins;
            right.Index += right.Wins;
            right.Remaining -= right.Wins;
            if (right.Remaining == 0)
            {
                return true;
            }
        }

        right.Array[dest++] = left.Array[left.Index++];
        if (--left.Remaining == 1)
        {
            return true;
        }

        return false;
    }
}