Задача g6_1023: Массивище

М. Густокашин
Во входном файле, через пробел даны числа A1, A2 ... An. Отсортировать эти числа по неубыванию и вывести отсортированный массив в выходной файл.

Входные данные
В первой строке входного файла дано число n (1<=n<=200000). Во второй строке через пробел записаны числа A1, A2 ... An (-15000<=A<=15000).
Выходные данные
В единственной строке выходного файла должен быть отсортированный массив.

Пример входного фалйа
4
4 3 1 2

Пример выходного файла
1 2 3 4

Решение g6_1023:
Это первая разобранная на сайте задача, условие которой я придумал сам! Итак, никакими стандартными средствами нам этот массив отсортировать не удастся. Сортировка слиянием, использование динамической памяти тоже не помогут (хотя кто их знает - сам не пробовал).
Идея состоит в том, что необходимо создать массив из элементов word размерностью от -15000 до 15000, изначально инициализированный нулями. При появлении очередного числа увеличиваем элемент массива с номером, равным этому числу на 1. При выводе просто проходим массив от -15000 до 15000 и выводим число, равное номеру массива столько раз, какое значение храниться в элементе с этим номером.

В этом решении есть ошибка. То есть не то что ошибка, а недоделка. А что если какое то число встречается больше 65537 раз. Тогда произойдет переполнение переменной word и восстановить массив станет невозможно! Чтобы избавиться от этой проблемы надо завести массив из 3 элементов integer, в которых будут храниться указатели на переполнившейся элемент массива. Переделать вывод результатов с использованием этого массива - задача несложная, поэтому здесь рассматриваться не будет ;)
Скачать тесты к задаче