Вы создаете изначально вектор размера 2е7, а все элементы массива добавляются ему в конец. Фактически, Вы просто сортируете набор нулей, поэтому и такой результат. Можно сделать изначально reserve() у вектора, но это не сильно улучшит результат.
Спасибо, что обратили внимание на мой недочет. Хотя ничего «странного» я здесь не вижу, просто не знал о существовании такого алгоритма построения. Бесспорно, нужно было перед тем, как решить, что реализация достаточно хороша, прочитать еще раз статью. Но сложно учесть все. А кучей пользуюсь редко (чтоб не сказать никогда), ее вполне заменяет дерево поиска.
Алгоритмы и так были сгруппированы, по скорости. Эта характеристика в рамках данной статьи более важна, чем, например, устойчивость, ведь цель определить именно скорости всех сортировок. С помощью этих результатов можно определить и лучшую среди устойчивых. Общая таблица — неплохая идея, наверное, я ее сделаю и выложу позже. Сортировка слиянием без дополнительной памяти есть (статья), но она вроде довольно сложная и не очень известная. Не могу я же я написать все известные человечеству алгоритмы )
Нужно было сделать столько запусков, чтобы это не заняло слишком много времени, и при этом давало достаточно надежные результаты. 20 — вполне подходящее число.
Пару раз за время тестирования система зависала на несколько минут, почему — не знаю.
Время измерялось встроенной в C++ функцией clock(), можете посмотреть в реализации.
Насчет Linux'а не знаю, у меня его нет.
Information
Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Пару раз за время тестирования система зависала на несколько минут, почему — не знаю.
Время измерялось встроенной в C++ функцией clock(), можете посмотреть в реализации.
Насчет Linux'а не знаю, у меня его нет.