вопрос по сортировке

[Wind Of Change]

как отсортировать n чисел, n может принимать значения от 0 до n^2, сложность алгоритма должна быть О(n)
?

[MBo]

поразрядная сортировка (radixSort) в n-ричной системе счисления
(в ней числа до n^2-1 имеют два разряда)

[Wind Of Change]

спасибо,
часто встречал задачи с вопросом какой лучше алгоритм сортировки использовать
есть ли где то материал который расказывает для каких задач, какой лучше использовать алгоритм?

[MBo]

http://algolist.ru/sort/index.php

В популярных учебниках по алгоритмам (Вирт, Ахо, Кормен, Седжвик) при рассмотрении алгоритмов сортировки указывается, на каких наборах данных они особенно эффективны