Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct slice
- {
- struct node *head;
- size_t size;
- };
- static void merge_down(struct linked_list *list,
- int (*cmp)(const void *, const void *), struct slice *top)
- {
- struct node *right = top->head;
- size_t count = top->size;
- --top;
- struct node *left = top->head;
- top->size += count;
- // determine merged list's head
- if(cmp(left->data, right->data) <= 0)
- {
- top->head = left;
- left = left->next;
- }
- else
- {
- top->head = right;
- struct node *node = right;
- right = right->next;
- remove_node(node, list);
- insert_before(node, list, left);
- --count;
- }
- while(left != right && count)
- {
- if(cmp(left->data, right->data) <= 0)
- left = left->next;
- else
- {
- struct node *node = right;
- right = right->next;
- remove_node(node, list);
- insert_before(node, list, left);
- --count;
- }
- }
- }
- static void sort(struct linked_list *list,
- int (*cmp)(const void *, const void *))
- {
- if(list->size < 2) return;
- struct slice stack[32];
- size_t top = -1;
- struct node *current = list->first;
- do
- {
- stack[++top] = (struct slice){ current, 1 };
- current = current->next;
- for(; top && stack[top-1].size <= stack[top].size; --top)
- merge_down(list, cmp, stack + top);
- } while(current);
- for(; top; --top)
- merge_down(list, cmp, stack + top);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement