LarrySort (https://github.com/LarryKiniu/larry-sort) implemented in C#

LarrySort.cs

#region Using

using System.Diagnostics;

#endregion

namespace LarrySort;

public static class Program
{
    public static void Main()
    {
        int[] test = {13, 1, 90, 102, 4, 7, 4, 59, 100, 201, 3, 77, 20, 62};
        LarrySort<int>(test);
        Debug.Assert(IsArraySorted(new GridSpanAbstraction<int>(test)));
    }

    private static bool IsArraySorted<T>(GridSpanAbstraction<T> arr) where T : IComparable
    {
        for (var i = 0; i < arr.Length - 1; i++)
        {
            T curr = arr[i];
            T next = arr[i + 1];
            if (curr.CompareTo(next) > 0) return false;
        }

        return true;
    }

    private static void DebugVisualizeGrid<T>(GridSpanAbstraction<T> arr, int gridSize)
    {
        var totalIdx = 0;
        for (var y = 0; y < gridSize; y++)
        {
            for (var x = 0; x < gridSize; x++)
            {
                Console.Write(arr[totalIdx] + " ");
                totalIdx++;
                if (totalIdx == arr.Length) break;
            }

            Console.Write("\n");
            if (totalIdx == arr.Length) break;
        }
    }

    public static void LarrySort<T>(GridSpanAbstraction<T> arr) where T : IComparable
    {
        int length = arr.Length;
        if (length == 1) return;
        if (length == 2)
        {
            T a = arr[0];
            T b = arr[1];
            if (a.CompareTo(b) > 0) (arr[0], arr[1]) = (arr[1], arr[0]);
            return;
        }

        var lengthSqrt = (int) MathF.Ceiling(MathF.Sqrt(length));

        // Step 1: Sort all even rows in ascending order, and odd in descending order.
        SortRows(arr, lengthSqrt);

        // Step 2: Sort all columns in ascending order.
        SortColumns(arr, lengthSqrt);

        // Step 3: Repeat steps (length + 1) times.
        for (var i = 0; i < length + 1; i++)
        {
            SortRows(arr, lengthSqrt);
            SortColumns(arr, lengthSqrt);
        }

        // Step 4: Walk the grid and reverse odd rows.
        for (var i = 0; i < lengthSqrt; i++)
        {
            bool evenRow = i % 2 == 0;
            if (evenRow) continue;

            int rowStartIdx = i * lengthSqrt;
            int rowEndIdx = Math.Min(arr.Length - 1, rowStartIdx + lengthSqrt - 1);
            ReverseInPlace(arr, rowStartIdx, rowEndIdx);
        }

        Debug.Assert(IsArraySorted(arr));
    }

    private static void SortRows<T>(GridSpanAbstraction<T> arr, int lengthSqrt) where T : IComparable
    {
        if (lengthSqrt == 2) // Manual sort for optimization.
        {
            T firstRowA = arr[0];
            T firstRowB = arr[1];
            int comparisonFirst = firstRowA.CompareTo(firstRowB);
            if (comparisonFirst > 0)
            {
                arr[0] = firstRowB;
                arr[1] = firstRowA;
            }

            if (arr.Length == 4)
            {
                T secondRowA = arr[2];
                T secondRowB = arr[3];
                int comparisonSecond = secondRowA.CompareTo(secondRowB);
                if (comparisonSecond < 0)
                {
                    arr[2] = secondRowB;
                    arr[3] = secondRowA;
                }
            }
        }
        else
        {
            for (var i = 0; i < lengthSqrt; i++)
            {
                bool even = i % 2 == 0;
                int rowStartIdx = i * lengthSqrt;
                int rowLength = Math.Min(arr.Length - rowStartIdx, lengthSqrt);

                GridSpanAbstraction<T> slice = arr.Slice(rowStartIdx, rowLength);
                LarrySort(slice);
                Debug.Assert(IsArraySorted(slice));

                // Reverse odd rows.
                if (even) continue;
                ReverseInPlace(slice);
            }
        }
    }

    private static void SortColumns<T>(GridSpanAbstraction<T> arr, int lengthSqrt) where T : IComparable
    {
        if (lengthSqrt == 2)
        {
            if (arr.Length == 4)
            {
                T firstColumnA = arr[0];
                T firstColumnB = arr[2];
                int comparisonFirst = firstColumnA.CompareTo(firstColumnB);
                if (comparisonFirst > 0)
                {
                    arr[0] = firstColumnB;
                    arr[2] = firstColumnA;
                }

                T secondColumnA = arr[1];
                T secondColumnB = arr[3];
                int comparisonSecond = secondColumnA.CompareTo(secondColumnB);
                if (comparisonSecond > 0)
                {
                    arr[1] = secondColumnB;
                    arr[3] = secondColumnA;
                }
            }
            else if (arr.Length == 3) // Align hole with second column.
            {
                T secondColumnA = arr[1];
                T secondColumnB = arr[2];
                int comparisonSecond = secondColumnA.CompareTo(secondColumnB);
                if (comparisonSecond > 0)
                {
                    arr[1] = secondColumnB;
                    arr[2] = secondColumnA;
                }
            }
        }
        else
        {
            for (var i = 0; i < lengthSqrt; i++)
            {
                var column = new GridSpanAbstraction<T>(arr, lengthSqrt, i);
                LarrySort(column);
                Debug.Assert(IsArraySorted(column));
            }
        }
    }

    private static void ReverseInPlace<T>(GridSpanAbstraction<T> arr, int start = 0, int end = -1)
    {
        if (end == -1) end = arr.Length - 1;
        while (start < end)
        {
            (arr[start], arr[end]) = (arr[end], arr[start]);
            start++;
            end--;
        }
    }
}

/// <summary>
/// Used to access and slice column arrays seamlessly.
/// </summary>
public class GridSpanAbstraction<T>
{
    public T[]? Source;
    public int Length = -1;

    public int ColumnMode = -1;
    public int RowLength = -1;
    public int LastRowIndex = -1;

    public GridSpanAbstraction<T>? Other;
    public int SliceOffset = -1;

    public T this[int key]
    {
        get
        {
            if (ColumnMode != -1)
            {
                int column = ColumnMode;
                if (LastRowIndex != -1 && key == Length - 1) column = LastRowIndex;

                key = key * RowLength + column;
                return Other![key];
            }

            if (Other != null) return Other[key + SliceOffset];

            return Source![key];
        }
        set
        {
            if (ColumnMode != -1)
            {
                int column = ColumnMode;
                if (LastRowIndex != -1 && key == Length - 1) column = LastRowIndex;

                key = key * RowLength + column;
                Other![key] = value;
                return;
            }

            if (Other != null)
            {
                key += SliceOffset;
                Other[key] = value;
                return;
            }

            Source![key] = value;
        }
    }

    protected GridSpanAbstraction()
    {
    }

    public GridSpanAbstraction(T[] src)
    {
        Source = src;
        Length = src.Length;
    }

    public GridSpanAbstraction(GridSpanAbstraction<T> src, int rowLength, int column)
    {
        Other = src;
        SliceOffset = 0;

        ColumnMode = column;
        RowLength = rowLength;

        int lastRowIndex = -1;

        var thisColumnLength = 0;
        var rows = (int) MathF.Ceiling((float) src.Length / rowLength);
        int holes = rowLength * rows - src.Length;
        for (var c = 0; c < rows; c++)
        {
            if (column % 2 != 0)
                if (holes > 0 && c == rows - 1) // Last column
                    if (column <= holes - 1)
                    {
                        break;
                    }
                    else
                    {
                        lastRowIndex = column - holes;
                        thisColumnLength++;
                        break;
                    }


            int index = c * rowLength + column;
            if (src.Length <= index) break;
            thisColumnLength++;
        }

        LastRowIndex = lastRowIndex;
        Length = thisColumnLength;
    }

    public GridSpanAbstraction<T> Slice(int start, int length)
    {
        Debug.Assert(start + length <= Length);

        var slice = new GridSpanAbstraction<T>
        {
            Other = this,
            Length = length,
            SliceOffset = start
        };
        return slice;
    }

    public static implicit operator GridSpanAbstraction<T>(T[] src)
    {
        return new GridSpanAbstraction<T>(src);
    }
}