#include <iostream>
#include <string>
#include <fstream>
#include <cmath>
#include <ctime>
#include <vector>
#include <iterator>
using namespace std;
const int maxN=20;
    const int bitsword = 32;
    const int bitsbyte = 8;
    const int bytesword = bitsword / bitsbyte;
    const int R = 1 << bitsbyte;
    int M = 10;
    inline int digit(int a, int d)
    {
        return (a >> bitsbyte * (bytesword - d - 1)) & (R - 1);
    }

#define bin(A) l+count[A]
template<class Item>
void insertion(Item a[], int l, int r) {
  Item x;
  long i, j;

  for ( i=0; i < (r-l); i++) {  // цикл проходов, i - номер прохода
    x = a[i];
        
    // поиск места элемента в готовой последовательности 
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];      // сдвигаем элемент направо, пока не дошли

    // место найдено, вставить элемент
    a[j+1] = x;
  }
}

template <class Item>
void _RadixMSDSort(Item a[], int l, int r, int d)
{
    int i, j, count[R + 1];
    static Item aux[maxN];

    if(d > bytesword)
         for(int p=0;p<100;p++)
  {
      int l=a[p];
      cout<<l<<" ";
        return;

    if(r - l <= M){
        insertion(a, l, r);
             for(int q=0;q<100;q++)
  {
      int t=a[q];
      cout<<t<<" ";
        return;
    }

    for(j = 0; j < R; j ++)
        count[j] = 0;

    for(i = l; i <= r; i ++)
        count[digit(a[i], d) + 1] ++;

    for(j = 1; j < R; j ++)
        count[j] += count[j - 1];

    for(i = l; i <= r; i ++)
        aux[l + count[digit(a[i], d)] ++] = a[i];

    for(i = l; i <= r; i ++)
        a[i] = aux[i];

    _RadixMSDSort(a, l, bin(0) - 1, d + 1);
    for(j = 0; j < R - 1; j ++)
        _RadixMSDSort(a, bin(j), bin(j + 1) - 1, d + 1);
}

template<class Item>
void RadixMSDSort(Item a[], int l, int r)
{
    M=r;
    _RadixMSDSort(a, l, r, 0);
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int n;
    cout<<"Введите колличество элиментов";cin>>n;
    int *A=new int[n];
    int l,r;
    
    for(int i=0;i<n;i++)
    {
        int z=10+rand()%(10-100+1);
        A[i]=z;
        //B[i]=z;
        cout<<z<<" "<<endl;
    }
    RadixMSDSort(A,0,n-1);
    system("pause");
    return 0;
}