#include <algorithm>
void sort(unsigned *a, int n) {
if(n == 1) return;
int r = n >> 1;
sort(a + r, n - r);
while (r != 1) {
int l = r >> 1;
sort(a, l);
int i = 0, j = r, k = r - l;
while (i != l && j != n) {
if (a[i] <= a[j]) std::swap(a[i++], a[k++]);
else std::swap(a[j++], a[k++]);
}
while (i != l) std::swap(a[i++], a[k++]);
while (j != n) std::swap(a[j++], a[k++]);
r = r - l;
}
for (int i = 0; i + 1 != n && a[i] > a[i + 1]; ++i) std::swap(a[i], a[i + 1]);
return;
}