struct list{
    int data;
    struct list *next;
};

struct list * insert(struct list *node, int data){
    struct list *tmp = (struct list*)malloc(sizeof(struct list));

    if (tmp != NULL){
        tmp->data = data;
        if (node != NULL){
            tmp->next = node->next;
            node->next = tmp;
        }else{
            tmp->next = NULL;
        }
    }

    return tmp;
}

struct list * sort(struct list *root){
    struct list *new_root = NULL;

    while (root != NULL){
        struct list *node = root;
        root = root->next;

        if (new_root == NULL || node->data < new_root->data){
            node->next = new_root;
            new_root = node;
        }else{
            struct list *current = new_root;
            while (current->next != NULL && !(node->data < current->next->data)){
              current = current->next;
            }

        node->next = current->next;
        current->next = node;
        }
    }

    return new_root;
}

void Sort(double a[], int n){
    if(a == NULL) return;
    int i, j;
    list **buckets = (list **)malloc(n*sizeof(list *)); /*Массив списков, сейчас содержит мусор*/
    memset(buckets, 0, n*sizeof(list *));   /*Проинициализируем его*/

    /*Вставить элемент a[i] в список buckets[floor(n*a[i])]*/
    for(i = 0; i < n; i++)
        insert(buckets[(int)floor(n*a[i])], a[i]);
    /*Сортировка всех списков*/
    for(i = 0; i < n; i++)
        buckets[i] = sort(buckets[i]);
    /*Слияние всех списков в один*/
    j = 0;
    /*Цикл по всем спискам*/
    list *p;
    for(i = 0; i < n ; i++){
        printf("end loopn");
        putchar('n');
        if(buckets[i] != NULL){
            p = buckets[i];
            while(p != NULL){
                printf("bucket[%d]: data %dn", i, p->data);
                a[j++] = p->data;
                p = p->next;
            }
        }else printf("bucket[%d] is emptyn", i);
    }
}