Сортировка вставкой в хэш-таблицу

И здесь тоже. Но опять немного по-другому. Ничто не ново под луной…

Сортировка вставкой в хэш-таблицу

Нашёл что-то похожее: Здесь. Но автор стремится к O(n) и поэтому делает вставки немного по-другому, используя матрицу.

Сортировка вставкой в хэш-таблицу

«устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами» — из вики. Два одинаковых значения здесь претендуют на одно и тоже место. При разрешении коллизий порядок одинаковых значений не изменяется.

В чем проблема-то? К чему здесь сравнение строк и корзины я вообще, извините, не понял.

Сортировка вставкой в хэш-таблицу

Спасибо за наводку. Не видел этого алгоритма. Действительно похож. Честно выводил сам.

Сортировка вставкой в хэш-таблицу

Не спорю ни разу. Надо всё хорошо померить, проанализировать, а потом и выводы делать.

Сортировка вставкой в хэш-таблицу

.

Сортировка вставкой в хэш-таблицу

Будет желание и время — проведу подробные замеры и построю графики. Просто решил поделиться в таком виде, чтобы не потерять вдохновение :)