Merge Sort a Linked List

Question

I was recently brushing up on some fundamentals and found merge sorting a linked list to be a pretty good challenge. If you have a good implementation then show it off here.

Answer 1

Wonder why it should be big challenge as it is stated here, here is a straightforward implementation in Java with out any "clever tricks".

//The main function public static Node merge_sort(Node head)  {     if(head == null || head.next == null)          return head;              Node middle = getMiddle(head);      //get the middle of the list     Node left_head = head;     Node right_head = middle.next;      middle.next = null;             //split the list into two halfs      return merge(merge_sort(left_head), merge_sort(right_head));  //recurse on that }  //Merge subroutine to merge two sorted lists public static Node merge(Node a, Node b) {     Node dummyHead = new Node();     for(Node current  = dummyHead; a != null && b != null; current = current.next;)     {         if(a.data <= b.data)          {             current.next = a;              a = a.next;          }         else         {              current.next = b;             b = b.next;          }              }     dummyHead.next = (a == null) ? b : a;     return dummyHead.next; }  //Finding the middle element of the list for splitting public static Node getMiddle(Node head) {     if(head == null)          return head;          Node slow = head, fast = head;          while(fast.next != null && fast.next.next != null)     {         slow = slow.next;         fast = fast.next.next;     }     return slow; } 

Answer 2

A simpler/clearer implementation might be the recursive implementation, from which the NLog(N) execution time is more clear.

typedef struct _aList {     struct _aList* next;     struct _aList* prev; // Optional.     // some data } aList;  aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two)) {     // Trivial case.     if (!list || !list->next)         return list;      aList *right = list,           *temp  = list,           *last  = list,           *result = 0,           *next   = 0,           *tail   = 0;      // Find halfway through the list (by running two pointers, one at twice the speed of the other).     while (temp && temp->next)     {         last = right;         right = right->next;         temp = temp->next->next;     }      // Break the list in two. (prev pointers are broken here, but we fix later)     last->next = 0;      // Recurse on the two smaller lists:     list = merge_sort_list_recursive(list, compare);     right = merge_sort_list_recursive(right, compare);      // Merge:     while (list || right)     {         // Take from empty lists, or compare:         if (!right) {             next = list;             list = list->next;         } else if (!list) {             next = right;             right = right->next;         } else if (compare(list, right) < 0) {             next = list;             list = list->next;         } else {             next = right;             right = right->next;         }         if (!result) {             result=next;         } else {             tail->next=next;         }         next->prev = tail;  // Optional.         tail = next;     }     return result; } 

NB: This has a Log(N) storage requirement for the recursion. Performance should be roughly comparable with the other strategy I posted. There is a potential optimisation here by running the merge loop while (list && right), and simple appending the remaining list (since we don't really care about the end of the lists; knowing that they're merged suffices).