#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

struct el
{
    int val;
    el*next,*prev;
};

struct stack
// структура, в которой хранятся промежуточные результаты сортировки 
{
    el*cur,*mass;
    int n,stackempty;
    stack();
    insert(int);
    release();
    reverserelease();
};

stack::stack()
// конструктор 
{
    n=0;
    cur=mass=NULL;
    stackempty=1;
}

stack::reverserelease()
// функция, которая возврящает первый элемент стэка,
// удаляет первый, и второй становится первым. 
{
    int ret;
    if(n==0)
        return 0;
    ret=mass->val;
    if(mass->next!=NULL){
        mass=mass->next;
        delete mass->prev;
    }
    else
        delete mass;
    n--;
    if(n==0)
        stackempty=1;
    return ret;
}

stack::release()
// функция, которая возврящает последний элемент стэка,
// удаляет последний, и последним становится предпоследний. 
{
    int ret;
    if(n==0)
        return 0;
    ret=cur->val;
    cur=cur->prev;
    if(cur==NULL)
        delete mass;
    else
        delete cur->next;
    n--;
    if(n==0)
        stackempty=1;
    return ret;
}

stack::insert(int ins)
// добавление элемента в стэк 
{
    stackempty=0;
    if(n==0){
        mass=new el;
        mass->prev=NULL;
        mass->next=NULL;
        mass->val=ins;
        cur=mass;
        n++;
        return 0;
    }
    cur->next=new el; 
    cur->next->prev=cur; 
    cur->next->next=NULL; 
    cur->next->val=ins; 
    cur=cur->next; 
    n++;
    return 0; 
}

void bitsort(int*p,int*numb,int len,int base) 
// собственно сортировка.
// p - указатель на исходный неотсотрированный массив
// numb - последовательность целых индексов в порядке возрастания от 0 до len-1
// фактически сортируется эта последовательность, а исходная не меняется.
// len - длина массива
// base - система счисления, по которой происходит сортировка. 
{
    int i,j,k,step;
    int bit,cbit;
    switch(base)
    {
//системой счисления определяется количество разрядов,
//по которым будет происходить сортировка.
//должна быть степенью двойки по понятным соображениям.
//здесь приведены не все возможные системы, кому мало, может дописать ещё.

        case 2: step=1; break; 
        case 4: step=2; break; 
        case 8: step=3; break; 
        case 16: step=4; break; 
        case 32: step=5; break; 
        case 512: step=9; break; 
        case 65536: step=16; break; 
        default: 
        printf("Error in sorting base: %d",base); 
        return; 
    }

    stack*st=new stack[base];
    for(i=0;i<sizeof(int)*8;i=i+step)
    { 
        cbit=(base-1)<<i;
        for(j=0;j<len;j++)
        {
            bit=p[numb[j]]&cbit;
            bit=bit>>i;
            st[bit].insert(numb[j]);
        }
        k=0; 

/*** вот этот кусок отвечает за построение возрастающей последовательности ***/
/**/       for(j=0;j<base;j++)
/**/       {
/**/            while(!st[j].stackempty)
/**/            {
/**/                numb[k]=st[j].reverserelease();
/**/                k++;
/**/            }
/**/        }
/*****************************************************************************/

//а здесь он заканчивается. 
        if(k!=len)
        { 
            printf("Error occured while sorting array");
            return; 
        }
    }
 delete st; 
}

// А вот начало нашей проги
void main()
{
    system("cls");
    int z = 0;
    int *p, *sorted, n = 0, i = 0, j = 0;
    stack st;
    unsigned int n_el = 0, max = 1024;
    clock_t start = 0,end = 0;
    float t1 = 0;

    n = 10/*0000*/;
    p = new int[n]; // выделяем память для значений
    sorted = new int[n]; // выделяем память для номеров отсортированных чисел
    
    srand((unsigned int)time(0l));
    for(i = 0; i < n; i++)
    {
        p[i] = rand(); // заполняем массив произвольными числами
        sorted[i] = i; // тоже заполняем
    }
// выводим сгенеренные значения
    for(i = 0; i < n; i++)
    {
        printf("%d\r\n",p[sorted[i]]);
    }

    printf("Press any key to begin sorting\r\n");
    _getch(); // просим нажать на any key

    start = clock(); // начинаем замер времени
    bitsort(p, sorted, n, 65536); // <=== сортируем здесь
    end=clock(); // заканчиваем подсчет времени

    t1 = (float)(end-start) / CLK_TCK; // считаем затраченное время в секундах
    printf("%lf\n",t1); // выводим результат
    
// выводим отсортированные значения
    for(i = 0; i < n; i++)
    {
        printf("%d\r\n",p[sorted[i]]);
    }

    delete p; // удаляем массив со значениями
    delete sorted; // удаляем массив с номерами отсортированных значений
    printf("Press any key to continue");
    while (!_getch()); // просим нажать на any key
}

    min=p[sorted[0]];

    for(j=base-1;j>=0;j--)
    {
        while(!st[j].stackempty)
        {
             numb[k]=st[j].release();
             k++;
        }
    }