UniLecs #170. Сортировка подсчетом

Задача: дан массив целых чисел из заданного диапазона [min, max]. Необходимо оптимальным способом отсортировать массив по возрастанию.

Входные данные: [min, max] - диапазон целых чисел, arr - массив целых чисел из заданного диапазона. min, max - не превышают 1000 по модулю. Размер массив от 1 до 10^6.

Вывод: отсортированный по возрастанию массив

Пример: диапазон чисел [1, 10]

arr =  [ 4, 5, 2, 2, 8, 9, 8, 2, 1, 4, 1, 4, 9 ]

Answer = [ 1, 1, 2, 2, 2, 4, 4, 4, 5, 8, 8, 9, 9 ]

Идея: отталкиваемся от того факта, что нам известен диапазон возможных чисел для сортировки и диапазон конечный. Поэтому мы можем отсортировать массив чисел сортировкой подсчет (counting sort).

Реализация:

https://gist.github.com/unilecs/1b4a5f0f72318f48b7532508b373fd90

Play-test: https://dotnetfiddle.net/1ImCnv