Last time I started with the simplest question of reversing a linked list this time let me go a bit further – sorting a linked list.

Just for a minute consider sorting a linked list , some of the standard sorting mechanism assumes random access of data (like quick sort, heapsort ) so linked list becomes a special case. But then we have one more wonderful sort left to consider , which is merge sort. 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);
}

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;
    }

View Comments to “Merge sort of linked list”

  • Great help…its work perfectly.

  • It seems that you just return the node but where is the linked list?

  • it seems getMiddle function exposes tricky behaviour, as I see it, it will return pointer to head for lists having two items, it means middle not fetched ;-) if you change behaviour of getMiddle function, the function merge_sort have to be also amended, but considering the fact that you might mean that getMiddle is not public and is strictly private, the code works

  • The reason why it might seem that the algorithms using O(1) space are complicated is because they are sorting on arrays – which will require O(n) space for a naive merge.

    However, your solution still uses O(Log n) space, albeit implicitly, hidden within the stack. A true O(1) space complexity algorithm would have implement merge sort purely using iteration. Your recursive solution will have a call depth of Log n. Hence it uses log n space.

    A better O(1) is also equally simple. What you would have to do here is to successively merge lists of size K, where K starts at 1 and doubles every iteration.

  • sorry i didn’t understand
    why
    middle.next = null
    after
    Node sHalf = middle.next

    why is it set to null ?

  • Ok (might be too late but), say the list is L=1->2->3->4->5 to split into lists A=1->2->3 and B=4->5.
    After calling splitList, we have middle=3 and middle.next=4. We want list B to start at 4, so sHalf=middle.next. We also want list A to end after the middle, so middle.next=null. Note that you have to use this order, not the other way around, cause in that case you’ll start list B at null.

  • A clarification perhaps. The assignment of the next node is a bit sloppy :) if I may say so:

    curr.next = b;

    If you use this algortithm literally, you will have an okay sorted list – or so it seems at first. Because the next is filled in correctly and that is what you use
    to print your list in order.
    However try printing it backwards :) . It will not be sorted so perfectly anymore …
    The reason is that you never set the previous correct, only the next.
    This can be solved by some trivial encapsulation:
    class Node{

    public void setNext(Node next){
    this.next = next;
    if(next != null)
    next.previous = this;
    }

    }

    Tadaaa!

    Only the new head node will still refer to the old previous because it is never set as next …
    So when finished sorting just do head.setPrevious(null);

    Sounds about right??

  • I think he’s assuming this is a singly linked list.

  • enormous@forte.garnet” rel=”nofollow”>.…

    tnx for info!!…

  • shameful@drivers.been” rel=”nofollow”>.…

    спс за инфу!…

  • squad@torquato.malice” rel=”nofollow”>.…

    спасибо….

  • boris@tulip.jag” rel=”nofollow”>.…

    спс….

  • threshing@carrots.jennies” rel=”nofollow”>.…

    благодарю!!…

  • recessed@maitre.juggling” rel=”nofollow”>.…

    сэнкс за инфу!!…

  • singer@peggin.ge” rel=”nofollow”>.…

    благодарю!!…

  • sick@aroused.kimbolton” rel=”nofollow”>.…

    thanks!…

  • poetically@contributed.vero” rel=”nofollow”>.…

    tnx….

  • riddles@dandily.minutemen” rel=”nofollow”>.…

    сэнкс за инфу!!…

  • Thanks for sharing your great solution! I have one problem though. My doubly linked list contains both head and tail references and after a merge sort with your solution the tail reference will be incorrect. I have already solved the head reference but I can’t figure out how to get the tail reference to point to the new last element. Any idea of how to do this? Many thanks

  • Nice logic it would work perfectly for single linked list….

Post comment

You must be logged in to post a comment.

blog comments powered by Disqus