mergesort.c

   1 #include "mergesort.h"
   2 #include "list.h"
   3
   4 void list_mergesort(struct list_head *head,
   5         int (*compare)(const struct list_head *, const struct list_head *))
   6 {
   7         LIST_HEAD(empty);
   8         struct list_head *unsorted_head, *sorted_head, *p, *q, *tmp;
   9         int psize, qsize, K, count;
  10
  11         if (list_empty(head))
  12                 return;
  13
  14         unsorted_head = head;
  15         sorted_head = &empty;
  16         K = 1;
  17         while (1) {
  18                 p = unsorted_head->next;
  19                 count = 0;
  20                 do {
  21                         q = p;
  22                         psize = 0;
  23                         while (psize < K) {
  24                                 if (q == unsorted_head)
  25                                         break;
  26                                 psize++;
  27                                 q = q->next;
  28                         }
  29                         qsize = K;
  30                         while (1) {
  31                                 struct list_head *e;
  32
  33                                 if (q == unsorted_head)
  34                                         qsize = 0;
  35                                 if (psize == 0 && qsize == 0)
  36                                         break;
  37                                 if (!psize || (qsize && compare(p, q) > 0)) {
  38                                         e = q;
  39                                         q = q->next;
  40                                         qsize--;
  41                                 } else {
  42                                         e = p;
  43                                         p = p->next;
  44                                         psize--;
  45                                 }
  46                                 list_del(e);
  47                                 list_add_tail(e, sorted_head);
  48                         }
  49                         count++;
  50                         p = q;
  51                 } while (p != unsorted_head);
  52
  53                 if (count == 1) {
  54                         head->next = sorted_head->next;
  55                         head->prev = sorted_head->prev;
  56                         sorted_head->prev->next = head;
  57                         sorted_head->next->prev = head;
  58                         return;
  59                 }
  60                 tmp = unsorted_head;
  61                 unsorted_head = sorted_head;
  62                 sorted_head = tmp;
  63                 K *= 2;
  64         }
  65 }