// bucket sort
// each bucket is sorted with std::sort
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
inline bool isDigit(char c) {
return c >= '0' && c <= '9';
}
// citire numar natural
int readInt(FILE* fin) {
char ch;
int res = 0;
// eliminam caracterele de dinaintea numarului (spatiu, rand nou, orice caracter care nu este cifra)
while (!isDigit(ch = fgetc(fin)));
// adaugam cifrele la numar pana cand caracterul citit nu mai este cifra
do {
res = 10 * res + ch - '0';
} while (isDigit(ch = fgetc(fin)));
return res;
}
#define MAX_N 500000
#define NO_VALUES (1 << 31)
#define NO_BUCKETS (1 << 16)
#define VALUES_PER_BUCKET (1 << 15)
#define VALUES_PER_BUCKET_BITS 15
int v1[MAX_N], v2[MAX_N];
int freq[NO_BUCKETS], ind[NO_BUCKETS];
inline int getBucketNumber(int value) {
return value >> VALUES_PER_BUCKET_BITS;
}
int main() {
FILE* fin = fopen("algsort.in", "r");
int n, i;
fscanf(fin, "%d", &n);
for (i = 0; i < n; ++i)
v1[i] = readInt(fin);
fclose(fin);
for (i = 0; i < n; ++i)
++freq[getBucketNumber(v1[i])];
for (i = 1; i < NO_BUCKETS; ++i)
ind[i] = ind[i - 1] + freq[i - 1];
for (i = 0; i < n; ++i)
v2[ind[getBucketNumber(v1[i])]++] = v1[i];
sort(v2 + 0, v2 + freq[0]);
for (i = 1; i < NO_BUCKETS; ++i) {
freq[i] += freq[i - 1];
sort(v2 + freq[i - 1], v2 + freq[i]);
}
FILE* fout = fopen("algsort.out", "w");
for (i = 0; i < n; ++i)
fprintf(fout, "%d ", v2[i]);
fclose(fout);
return 0;
}