Guest User

Linked-list merge sort

a guest
Jan 6th, 2014
252
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. node_t **mergesort(node_t **list, size_t count) {
  2.     size_t half = count >> 1;
  3.     if(half) {
  4.         // Divide and recursively sort the two halves, returning links to the final
  5.         // elements as by-products
  6.         node_t **first_tail = mergesort(list, half);
  7.         node_t *first_head = *list;
  8.         node_t **second_tail = mergesort(first_tail, count - half);
  9.         node_t *second_head = *first_tail;
  10.  
  11.         // Merge the two halves, chaining in the smaller of the two front-most
  12.         // elements from the two lists
  13.         for(;;) {
  14.             // Prefer the first list in case of equality for stability
  15.             if(first_head->key <= second_head->key) {
  16.                 *list = first_head;
  17.                 list = &first_head->next;
  18.                 // Stop once a half list has been exhausted
  19.                 if(&first_head->next == first_tail) {
  20.                     // Chain in the rest of the second list as-is
  21.                     *list = second_head;
  22.                     return second_tail;
  23.                 }
  24.                 first_head = *list;
  25.             } else {
  26.                 *list = second_head;
  27.                 list = &second_head->next;
  28.                 if(&second_head->next == second_tail) {
  29.                     // We're ending with items from the first list so a special
  30.                     // case is required to shuffle the final link pointing outside
  31.                     // of list section being processed
  32.                     *first_tail = *list;
  33.                     *list = first_head;
  34.                     return first_tail;
  35.                 }
  36.                 second_head = *list;
  37.             }
  38.         }
  39.     }
  40.     // Stop once there's only a single item in the list. On entry with an empty list
  41.     // this returns invalid data, deal with that case separately if a pointer to the
  42.     // end is required as output
  43.     return &(*list)->next;
  44. }
RAW Paste Data