23

# Merge sort of linked list

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

```
```

Sahilsays:Great help…its work perfectly.

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

alexsays: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

Sid Balasays: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.

Guestsays:sorry i didn’t understand

why

middle.next = null

after

Node sHalf = middle.next

why is it set to null ?

adinutzycsays: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.

ruben056says: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??

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