Merge sort of linked list « Think !

Merge sort of linked list « Think !

Once you make a decision, the universe conspires to make it happen. 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,

Read full article from Merge sort of linked list « Think !