/* Функция сортировки подсчетом.
    *
    *  Параметры:
    *  a - указатель на массив
    *  N - номер последнего элемента
    *  Заметка:
    *  Элементы массива должны быть уникальны (ограничение алгоритма).
    */
    template <class Ty> void CountingSort(Ty* a, int N)
    {
        // выделяем вспомогательный массив
        Ty* tmp = new Ty[N+1];

        for (int i=0; i<=N; ++i)
        {
            // количество элементов меньших a[i]
            int k = 0; 

            for (int j=0; j<i; ++j) if (a[j] < a[i]) ++k;
            for (int j=i+1; j<=N; ++j) if (a[j] < a[i]) ++k;

            // вставляем a[i] на место k+1
            tmp[k] = a[i];
        }

        // копируем значения из вспомогательного массива в основной
        memcpy(a, tmp, (N+1) * sizeof(Ty));
        delete [] tmp;
    }