Sort a linked list using merge sort

 Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.

We have discussed the sorting options for linked list here.

Merge sort is very special (in fact many standard sort libraries like in java internally uses a combination of merge sort and insertion sort) because it has the wonderful property of being a stable sort. In fact it is the only stable sort with asymptotic complexity of O(nlogn) but its draw back typically is the use of O(n) extra space. There are wonderful inline merge sort algorithms which I would cover in a different post altogether. Now what is more wonderful is that for sorting linked list, we can use merge sort’s O(nlogn) without the drawback of O(n) space. Again a quick search in net seem to suggest it is a very complicated algorithm to implement , again I am not sure why , this is my version of it (in Java).
The basic idea of merge sort is this basic recursive idea , how most of us learned recursion to start with -

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

The merge algorithm on linked lists is really beautiful. The pseudocode works roughly like this:

1. Initialize an empty linked list holding the result.
2. As long as both lists aren't empty:
   1. If the first element of the first list is less than the first element of the second list, move it to the back of the result list.
   2. Otherwise, move the first element of the second list to the back of the result list.
3. Now that exactly one list is empty, move all the elements from the second list to the back of the result list.

This can be made to run in O(n) time, so the overall complexity of the merge sort is O(n log n).
A working implementation in Java :

public Node merge_sort(Node head) {
    if(head == null || head.next == null) { return head; }
    Node middle = getMiddle(head);      //get the middle of the list
    Node sHalf = middle.next; middle.next = null;   //split the list into two halfs

    return merge(merge_sort(head),merge_sort(sHalf));  /recurse on that
}

public Node merge(Node a, Node b) {
    Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
    while(a !=null && b!= null) {
        if(a.info <= b.info) { curr.next = a; a = a.next; }
        else { curr.next = b; b = b.next; }
        curr = curr.next;
    }
    curr.next = (a == null) ? b : a;
    return dummyHead.next;
}

public Node getMiddle(Node head) {
    if(head == null) { return head; }
    Node slow, fast; slow = fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    return slow;
}

Thanks

source - http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list/
http://stackoverflow.com/questions/7168164/sorting-linked-lists-in-c/7168300#7168300