Сортировка подсчётом с восстановлением порядка

Java Сложный sorting

Задача «Сортировка подсчётом с восстановлением порядка»

Дан массив целых чисел. Необходимо отсортировать его по возрастанию, используя алгоритм сортировки подсчётом (counting sort). Однако при одинаковых значениях элементов необходимо сохранить их исходный относительный порядок (стабильная сортировка). Выведите отсортированный массив. Ограничения: длина массива от 1 до 10^5, значения элементов от -10^4 до 10^4.

Формат ввода

Первая строка содержит целое число N (1 ≤ N ≤ 100000) — количество элементов. Вторая строка содержит N целых чисел, разделённых пробелами — элементы массива.

Формат вывода

Выведите N чисел — отсортированный массив, разделённых пробелами.

Примеры

Пример 1

ВВОД

5
3 1 2 1 3

ВЫВОД

1 1 2 3 3

Пример 2

ВВОД

4
-2 0 -2 1

ВЫВОД

-2 -2 0 1

Пример 3

ВВОД

1
42

ВЫВОД

42

main.java