Суть: для каждого элемента массива считаем сколько раз он встретился, а потом формируем массив

[https://github.com/il-bychkov/algorithms](https://lh7-us.googleusercontent.com/3bbc9cqDYMKq8TlPtRaWTGPXiCoeJLI-yOoyzbLE_0M28RCCW0boI0l3welXhDxsUWDoVBOp48hT7RQWRZnebMINSTUyTcIh3WuqEN6l0kuEFoz8d4-VO_PgA4l-1iyjcosOiglXWh57qOs__mnXJw)

https://github.com/il-bychkov/algorithms

1 шаг – устанавливаем диапазон, заводим второй массив, где количество элементов равно диапазону. Пример: “counting_arr[3] = 5” — элемент “3” встретился 5 раз.

2 шаг – проходим изначальный массив, каждый раз увеличивая счетчик в элементе второго массива под индексом соответствующему элементу первого массива

3 шаг – проходим по второму массиву, смотрим сколько раз встретился каждый элемент, записываем элемент соответствующее количество раз в новый массив (или перезаписываем изначальный)

Сложность по времени: $O(n+k)$

Но зависит именно от входных данных: если больше диапазон, то он будет тянуть время, если чисел много, то они будут тянуть время.

n – количество входных чисел***,*** k **– количество вариантов этих чисел