Здравствуйте, Ikemefula, Вы писали:

I>Странно, http://rsdn.org/forum/flame.comp/6907242.1

Автор: Ikemefula
Дата: 18.09.17

Смотрим дату — 18го сентября. На этот момент была только одна версия — самая первая, где const вместо let (что порвало тебе одно место).

Облажался ты, а виноват почему-то я.

I>Какой рантайм — экспериментальный, ближе всего к нему будет наверное node 8.8.1 64, точнее не могу сказать. На самом деле уже не важно. И вот почему — я позапускал эту версию от 19го сентября на разных компах с разной производительностью и сортировка везде укладывается в 1600+- 200 мс.

Надо же, какой магический рантайм. Скорость от железа вообще не зависит.
Хотя нет, я в магию не верю. Так что вся магия наверняка заключается в каком-то очень особом способе измерения.

I>Более того — даже разные рантаймы дают очень похожее число, колебания в пределах 15%.

Разброс даже на том же самом железе и той же версии рантайма +-25%.

I>Если мы про алгоритмы, то их принято доказывать, что они являются тем, что надо

Элементарно, если тебе яйца танцевать мешают или еще какие проблемы подобного характера.
Из 300 случайных тестовых наборов по миллиону записей, ноль ошибок. А теперь, вероятно, ты опять начнешь юлить и выкручиваться?

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Text;

namespace QuickSort
{
    public static class SortingCheck
    {
        public static void Test()
        {
            var itemsCount = 1000_000;

            int Compare(TestClass x, TestClass y) => string.CompareOrdinal(x.Id, y.Id);

            for (var i = 0; ; i++)
            {
                var vals = Enumerable.Range(0, itemsCount).Select(x => new TestClass()).ToArray();
                QuickSort(vals, Compare);
                Check(vals, Compare);
                Console.WriteLine($"Run finished: {i}");
            }
        }

        public static void Check<T>(IList<T> vals, Func<T, T, int> compare)
        {
            for (var i = 1; i < vals.Count; i++)
            {
                if (compare(vals[i - 1], vals[i]) > 0)
                    throw new ApplicationException();
            }
        }

        public static void QuickSort<T>(T[] vals, Func<T, T, int> compare)
        {
            QuickSort(vals, compare, 0, vals.Length - 1);
        }

        public static void QuickSort<T>(T[] vals, Func<T, T, int> compare, int left, int right)
        {
            if (right <= left)
                return;

            var i = left;
            var j = right;
            var mid = (int)(((long)left + right) / 2);
            var midVal = vals[mid];

            while (i <= j)
            {
                while (compare(vals[i], midVal) < 0)
                {
                    i++;
                }

                while (compare(vals[j], midVal) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    var tmp = vals[i];
                    vals[i] = vals[j];
                    vals[j] = tmp;

                    i++;
                    j--;
                }
            }

            QuickSort(vals, compare, left, j);
            QuickSort(vals, compare, i, right);
        }

        class TestClass
        {
            public readonly string Id;
            public readonly string Value;

            public TestClass()
            {
                Id = CreateId();
                Value = CreateId();
            }

            static readonly Random RandomGen = new Random();

            static string CreateId()
            {
                var num = (long)Math.Floor(RandomGen.NextDouble() * Math.Pow(10, 16));
                var res = num.ToString(Format, CultureInfo.InvariantCulture);
                return res;
            }

            static readonly string Format = new string('0', 8);

            public override string ToString()
            {
                return Id;
            }
        }
    }
}