計算量O(n)で噂のスターリンソートを実装してみた

using System;
using System.Collections.Generic;

#nullable enable
namespace CSharp
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello Stalin!");
            WriteStalinSort(new[] { 4 });
            WriteStalinSort(new[] { 6, 2, 5, 7, 3, 8, 8, 4 });
            WriteStalinSort(new[] { 5, 3, 7, 8, 9, 5, 3, 5, 7 });
            /**
             * Hello Stalin!
             * Input: 4
             * StalinBy: 4
             * StalinByDescending: 4
             * Input: 6, 2, 5, 7, 3, 8, 8, 4
             * StalinBy: 6, 7, 8, 8
             * StalinByDescending: 6, 2
             * Input: 5, 3, 7, 8, 9, 5, 3, 5, 7
             * StalinBy: 5, 7, 8, 9
             * StalinByDescending: 5, 3, 3
             */
        }

        public static void WriteStalinSort(int[] source)
        {
            Console.WriteLine($"Input: {string.Join(", ", source)}");
            Console.WriteLine($"StalinBy: {string.Join(", ", source.StalinBy(x => x))}");
            Console.WriteLine($"StalinByDescending: {string.Join(", ", source.StalinByDescending(x => x))}");
        }
    }

    public static class StalinSort
    {
        public static IReadOnlyList<TSource> StalinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return source.StalinBy(keySelector, Comparer<TKey>.Default);
        }

        public static IReadOnlyList<TSource> StalinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            return stalinSort(source, keySelector, comparer, false);
        }

        public static IReadOnlyList<TSource> StalinByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return source.StalinByDescending(keySelector, Comparer<TKey>.Default);
        }

        public static IReadOnlyList<TSource> StalinByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            return stalinSort(source, keySelector, comparer, true);
        }

        private static IReadOnlyList<TSource> stalinSort<TSource, TKey>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
        {
            if (source is null)
            {
                throw new ArgumentNullException(nameof(source));
            }
            if (keySelector is null)
            {
                throw new ArgumentNullException(nameof(keySelector));
            }
            if (comparer is null)
            {
                throw new ArgumentNullException(nameof(comparer));
            }

            IList<TSource> result = new List<TSource>();
            using IEnumerator<TSource> enumerator = source.GetEnumerator();

            if (enumerator.MoveNext())
            {
                TSource element = enumerator.Current;
                TKey lastKey = keySelector(element);

                result.Add(element);

                while (enumerator.MoveNext())
                {
                    element = enumerator.Current;
                    TKey newKey = keySelector(element);
                    int compare = descending ? comparer.Compare(lastKey, newKey) : comparer.Compare(newKey, lastKey);

                    if (0 <= compare)
                    {
                        result.Add(element);
                        lastKey = newKey;
                    }
                }
            }

            return (IReadOnlyList<TSource>)result;
        }
    }
}

fun main(args: Array<String>) {
    println("Hello Stalin!")
    writeStalinSort(intArrayOf(4))
    writeStalinSort(intArrayOf(6, 2, 5, 7, 3, 8, 8, 4))
    writeStalinSort(intArrayOf(5, 3, 7, 8, 9, 5, 3, 5, 7))
    /**
     * Hello Stalin!
     * Input: 4
     * StalinBy: 4
     * StalinByDescending: 4
     * Input: 6,2,5,7,3,8,8,4
     * StalinBy: 6,7,8,8
     * StalinByDescending: 6,2
     * Input: 5,3,7,8,9,5,3,5,7
     * StalinBy: 5,7,8,9
     * StalinByDescending: 5,3,3
     */
}

private fun writeStalinSort(source: IntArray) {
    println("Input: ${source.joinToString(",")}")
    println("StalinBy: ${source.asSequence().stalinBy().joinToString(",")}")
    println("StalinByDescending: ${source.asSequence().stalinByDescending().joinToString(",")}")
}

fun <T> Sequence<T>.stalinBy(): List<T> where T : Comparable<T> {
    return stalinSort(this, false)
}

fun <T> Sequence<T>.stalinByDescending(): List<T> where T : Comparable<T> {
    return stalinSort(this, true)
}

private fun <T> stalinSort(source: Sequence<T>, descending: Boolean): List<T> where T : Comparable<T> {
    val iterator = source.iterator()
    val result = mutableListOf<T>()

    if (iterator.hasNext()) {
        var lastElement = iterator.next()
        result.add(lastElement)

        while (iterator.hasNext()) {
            val element = iterator.next()
            val compare = when (descending) {
                true -> element <= lastElement
                false -> lastElement <= element
            }
            if (compare) {
                result.add(element)
                lastElement = element
            }
        }
    }

    return result
}

# Crystal 0.27.2 [60760a546] (2019-02-05)
# LLVM: 4.0.0
# Default target: x86_64-unknown-linux-gnu

puts "Hello Stalin!"
write_stalin_sort [4]
write_stalin_sort [6, 2, 5, 7, 3, 8, 8, 4]
write_stalin_sort [5, 3, 7, 8, 9, 5, 3, 5, 7]

# Hello Stalin!
# Input: [4]
# StalinBy: [4]
# StalinByDescending: [4]
# Input: [6, 2, 5, 7, 3, 8, 8, 4]
# StalinBy: [6, 7, 8, 8]
# StalinByDescending: [6, 2]
# Input: [5, 3, 7, 8, 9, 5, 3, 5, 7]
# StalinBy: [5, 7, 8, 9]
# StalinByDescending: [5, 3, 3]

def write_stalin_sort(source : Array(Int32))
  puts "Input: #{source}"
  puts "StalinBy: #{stalin_by source}"
  puts "StalinByDescending: #{stalin_by_descending source}"
end

def stalin_by(source : Array(Int32))
  stalin_sort source, false
end

def stalin_by_descending(source : Array(Int32))
  stalin_sort source, true
end

def stalin_sort(source : Array(Int32), descending : Bool)
  if source.size <= 1
    return source
  end

  result = Array(Int32).new
  lastElement = source[0]
  result << lastElement

  i = 1
  while i < source.size
    element = source[i]
    compare = if descending
                element <= lastElement
              else
                lastElement <= element
              end
    if compare
        lastElement = element
        result << element
    end

    i += 1
  end

  result
end