Algorithms and Data Structures

Counting Sort

Algorithms like Merge Sort perform operations to sort a given sequence of elements. Most of the built-in sort() functions in different programming languages perform operations as well. A natural question arises - is there any way to perform sorting more quicker?
One basic algorithm that sorts a sequence of elements in linear time, meaning that it performs operations, is the Counting Sort algorithm. Counting sort is an efficient, linear-time sorting algorithm that is particularly well-suited for sorting a collection of items where the values are known to be small integers.
The basic idea behind counting sort is to use a histogram-like structure to count the number of items in the input collection that have a given value, and then use this information to reorder the items in the input into the desired sorted order.
So, to sort an array with values [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], we would create a histogram that would show that there are 6 ones, 2 twos, 5 threes, etc: [6, 2, 5, 4, 5, 1, 6, 1] (like presented in the picture).
notion image
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 `num`s to result as the value in the histogram
In the end, the result will have the value [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].
Note that this approach would work for only numbers, specifically small numbers, while other algorithms like Bubble sort or Merge sort work on arbitrary elements that can be compared to each other.
So, the algorithm performs operations in total, where n is the number of elements in the initial array, while r is the size of the range of the values in the given array. This can be especially fast compared to algorithms like Merge sort when working with numbers that have a relatively small range of values.
🤔
Are there other linear-time algorithms for sorting? Yes, you can have a look at Radix-sort. Yet, they only work for numbers. If we take only comparison-based algorithms, that can work on any type of sequence, and the only thing required is being able to compare the items in the given sequence, then the best algorithm can perform operations, not less.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ).
The next line contains n space-separated integers (-100 ≤ ≤ 100).

Output

The program should print the given n integers separated by a space in increasing order.

Examples

Input
Output
5 -3 5 -1 2 10
-3 -1 2 5 10
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 5 MB

To check your solution you need to sign in