void counting_sort(int a[], int n) {
    //TODO: write your stable counting sort here (only positive numbers)
    int max;
    max = find_max(a, n); // Максимальное число в массиве.
    /* Ограничимся поиском только максимума, так как
    ТЗ не требует работы для отрицательных чисел и смещения
    для положительных чисел. Под смещением имеется ввиду рассмотрение
    только тех чисел, которые есть в диапозоне массива.
    */
    int *b; // Массив результата
    int *c; // Массив для подсчета
    c = new int[max+1]; // c[i] - количество i в массиве a.
    fill_zero(c, max+1);
    for (int i = 0; i < n; i++) // Подсчет
        c[a[i]]++;
    for (int i = 1; i <= max; i++)
        c[i]+=c[i-1];

    b = new int[n];
    for (int i = n - 1; i >= 0; i--)
    {
        b[c[a[i]] - 1] = a [i];
        c[a[i]]--;
    }
    memcpy(a, b, sizeof (int) *n); // заменяем исходный массив на результат
    delete [] c;
    delete [] b;// высвобождение памяти
}

void radix_sort256(int a[], int n) {
    //TODO: write your radix sort here (256 number system, only positive numbers)
    union auxiliaryUnion
    {
        int num;
        unsigned char uc[4];
    };
    int NUMBERS_IN_BYTE = 256; // 1 byte
    auxiliaryUnion *aux, *b;
    aux = new auxiliaryUnion[n]; // подаетеся на вход
    b = new auxiliaryUnion[n]; // записываем ответ
    for (int i = 0; i < n; i++) // Заполняем массив
        aux[i].num = a[i];
    int *c;
    c = new int [NUMBERS_IN_BYTE]; // Массив для подсчета
    for (int k = 0; k < 4; k++) // Сортировка 4 байтов, начиная с младшего
    {
        fill_zero(c, NUMBERS_IN_BYTE);
        for (int i = 0; i < n; i++) // Подсчет
            c[aux[i].uc[k]]++;
        for (int i = 1; i < NUMBERS_IN_BYTE; i++)
            c[i]+=c[i-1]; //Стойкость
        for (int i = n - 1; i >= 0; i--)
        {
            b[c[aux[i].uc[k]] - 1].num = aux[i].num; // Заполнение ответа.
            c[aux[i].uc[k]]--;
        }
        memcpy(aux, b, sizeof (int) * n);
    }
    memcpy(a, aux, sizeof (int) * n);
    delete [] c;
    delete [] aux;
    delete [] b; // Высвобождаем память
}

int find_max (int a[], int n) { // Поиск максимума в массиве
    int max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] > max)
            max = a[i];
    }
    return max;
}

void fill_zero (int a[], int n) { // Заполнение массива нулями
    for (int i = 0; i < n; i++)
        a[i] = 0;
}