Как быстро вы можете отсортировать n элементов в диапазоне {1,2, ... n ^ 2), учитывая пространство памяти O (n)?

Question

Я думаю об использовании сортировки по счетам.Но я не думаю, что это ответ, так как k, в данном случае, это n ^ 2.Таким образом, время сортировки будет O (n + n ^ 2).Также я думаю, что это превысит лимит хранения.

Есть идеи?

Спасибо.

Answer 1

Вы можете использовать сортировку с восходящим слиянием для достижения этого, которая выполняется в O (n log n), не требуя дополнительного пространства (так как оно на месте).

Answer 2

Вы можете использовать слегка модифицированную версию Merge Sort , чтобы разделить список на n частей вместо половин.Временная сложность сортировки слиянием составляет O (n log n), но я не знаю, как получить отредактированную версию.
Если кто-то мне поможет, я добавлю его в свой ответ:)

РЕДАКТИРОВАТЬ:
Кажется, кто-то уже изобрел это, см. Ответ @ JSPerfUnkn0wn