Сортировка n чисел между [0, n ^ 2 - 1] в O (n)?

Возможный дубликат:
An array of length N can contain values 1,2,3 … N^2. Is it possible to sort in O(n) time?

Учитывая n числа в диапазоне [0,n^2 -1], как мы можем отсортировать их в O (n) времени выполнения?

У меня такое ощущение, что решение включает radix sort, но я все еще ничего не вижу.

Номера n являются целыми числами.

Любые идеи?

Замечание: не домашнее задание!

Привет

Фактическое время будет зависеть от распределения данных, которые у вас есть, но я бы сделал следующее:

Сделайте n ковшей.
Пройдите через каждое число и поместите элемент со значением я в bucket sqrt (i).
Пройдите через каждое ведро и выполните сортировку по основанию для каждого элемента в ковше.

Я думаю, тебе не повезло. Radix sort - это O (k * n), где k - количество цифр. В вашем случае k = log (n ^ 2), что приводит к O (n * log (n)).