Сортировку массива с элементами в диапазоне от 0 до 9999

Я недавно наткнулся на проблему C ++. Итак,

Предположим, вы знаете, что все значения в целочисленном массиве попадают в диапазон от 0 до 9999. Покажите, что можно написать алгоритм O (N) для сортировки массивов с этим ограничением

Насколько я понимаю, алгоритм O (N) - это алгоритм, в котором вы выполняете определенный набор O (1) операций N раз. Теперь хоть убей, я не могу понять, как бы вы написали программу, которая сортирует массив чисел относительно O (N). Сортировка в своей самой простой форме состоит из сравнения чисел друг с другом, и нет алгоритма для выполнения этого за одну итерацию и получения отсортированного массива.

В вопросе говорится, что элемент этого массива может только имеют значение в диапазоне 0-9999. Из вопроса я могу понять, что именно это ограничение делает все возможным, и я должен использовать его в моем алгоритме, чтобы найти решение. Но я все еще ничего не добился. Все известные мне алгоритмы сортировки (Selection, Insertion, Merge, Quick ...) имеют время работы больше, чем O (N), с минимальным значением O (log N).

Я могу понять, что некоторые из этих алгоритмов могут иметь время работы O (N), но только в лучших случаях. Но я не думаю, что этот вопрос задают в этом отношении.

Если кто-нибудь может пролить свет на эту проблему, я был бы признателен.