Counting Sort

Алгоритмы, подобные Merge Sort, выполняют операций, чтобы отсортировать заданную последовательность элементов. Большинство встроенных функций sort() в разных языках программирования также работают за . Возникает закономерный вопрос — можно ли отсортировать ещё быстрее?

Один из базовых алгоритмов, который умеет сортировать последовательность элементов за линейное время (то есть выполняет операций), — это Counting Sort (сортировка подсчётом). Такой подход особенно эффективен, когда мы имеем дело с набором элементов, представляющих собой небольшие целые числа.

Основная идея Counting Sort заключается в том, чтобы с помощью структуры, напоминающей гистограмму, подсчитать, сколько раз встречается каждое возможное значение во входном массиве. После этого на основе полученных подсчётов элементы массива распределяются в итоговую последовательность в отсортированном порядке.

Например, чтобы отсортировать массив со значениями [7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], мы строим гистограмму, которая показывает количество каждого числа, встречающегося в массиве, к примеру: [6, 2, 5, 4, 5, 1, 6, 1] (как показано на рисунке).

a = ...

bottom, top = min(a), max(a) + 1       # Determine the range
hist = [0] * (top - bottom)            # Fill the range with 0s => no counts
for num in a:                          # Iterate through the array
    hist[num - bottom] += 1            # Increase the histogram value

res = []                               # Initialize the result array
for num in range(bottom, top):         # Iterate over the range
    res += [num] * hist[num - bottom]  # Add as many nums to result as the value in the histogram

В результате получится массив [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].

Обратите внимание: такой подход работает только с числами, причём желательно с небольшим диапазоном значений. В то же время, другие алгоритмы вроде Bubble sort или Merge sort могут обрабатывать любые элементы, которые можно сравнивать между собой.

Таким образом, алгоритм Counting Sort в сумме выполняет операций, где n — это количество элементов в исходном массиве, а r — размер диапазона возможных значений. Когда диапазон сравнительно небольшой, это может работать значительно быстрее, чем, к примеру, Merge sort.

Входные данные

В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ ).

Во второй строке указаны n целых чисел (-100 ≤ ≤ 100).

Выходные данные

Программа должна вывести n чисел, расположенных по возрастанию, разделяя их одним пробелом.

Примеры