自然順ソート (Natural sort order) を行う `IComparer<T>` の実装。

NaturalSortComparer.cs

#nullable enable

using System;
using System.Collections.Generic;

namespace Commons {

    /// <summary>
    /// 自然順ソート (Natural sort order) を行う <see cref="IComparer{T}"/> の実装。
    /// cf. https://ja.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E9%A0%86
    /// </summary>
    public class NaturalSortComparer : IComparer<string?> {
        private readonly EnumerableComparer<Block> _comparer;

        /// <summary>
        /// Initializes a new instance of the <see cref="NaturalSortCompare"/> class.
        /// <para>文字列の比較は、現在のカルチャを使用して大文字と小文字を区別して行います。</para>
        /// </summary>
        public NaturalSortComparer() : this(StringComparison.CurrentCulture) { }

        /// <summary>
        /// Initializes a new instance of the <see cref="NaturalSortCompare"/> class.
        /// </summary>
        /// <param name="comparison">文字列の比較子。</param>
        public NaturalSortComparer(StringComparison comparison) {
            _comparer = new EnumerableComparer<Block>(new BlockComparer(comparison));
        }

        /// <inheritdoc />
        public int Compare(string? x, string? y) {
            if (x == y) { return 0; }
            if (x is null) { return -1; }
            if (y is null) { return 1; }
            if (x is "") { return -1; }
            if (y is "") { return 1; }

            IEnumerable<Block>? xBlocks = Split(x);
            IEnumerable<Block>? yBlocks = Split(y);

            return _comparer.Compare(xBlocks, yBlocks);
        }

        /// <summary>文字列を <see cref="Block"/> のシーケンスに分割。</summary>
        private static IEnumerable<Block>? Split(string? value) {
            if (value is null) { return null; }
            if (value is "") { return Array.Empty<Block>(); }

            return Internal();

            IEnumerable<Block> Internal() {
                int prevIndex = 0;
                BlockType prevType = char.IsDigit(value, 0) ? BlockType.Numeric : BlockType.Other;

                for (int i = 1; i < value.Length; i++) {
                    BlockType type = char.IsDigit(value, i) ? BlockType.Numeric : BlockType.Other;
                    if (prevType == type) { continue; }

                    yield return new Block(value.Substring(prevIndex, i - prevIndex), prevType);
                    prevIndex = i;
                    prevType = type;
                }

                yield return new Block(value.Substring(prevIndex), prevType);
            }
        }

        /// <summary>特定の文字種で構成された文字列ブロック。</summary>
        private readonly struct Block {
            public readonly string Value;
            public readonly BlockType Type;

            public Block(string value, BlockType type) {
                Value = value;
                Type = type;
            }
        }

        private enum BlockType : byte {
            Unspecified,
            Numeric,
            Other,
        }

        /// <summary><see cref="Block"/> の比較子。</summary>
        private readonly struct BlockComparer : IComparer<Block> {
            private readonly StringComparison _comparison;

            public BlockComparer(StringComparison comparison) {
                _comparison = comparison;
            }

            public int Compare(Block x, Block y) {
                switch ((x.Type, y.Type)) {
                    case (BlockType.Other, BlockType.Other):
                        return string.Compare(x.Value, y.Value, _comparison);

                    case (BlockType.Other, BlockType.Numeric):
                        return 1;

                    case (BlockType.Numeric, BlockType.Other):
                        return -1;
                }

                string xv = x.Value.TrimStart('0');
                string yv = y.Value.TrimStart('0');

                switch (xv.Length - yv.Length) {
                    case < 0:
                        return -1;

                    case > 0:
                        return 1;

                    case 0 when xv == yv:
                        return string.Compare(x.Value, y.Value, _comparison);

                    case 0:
                        return string.Compare(xv, yv, _comparison);
                }
            }
        }
    }
}

#nullable restore