[Solved]: Sort doubly linked list efficiently

Problem Detail: 

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?

Asked By : Rishika

Answered By : FrankW

Mergesort keeps its $\Theta(n\log n)$ worst case on linked lists. Double-linking can't help (except perhaps by improving the constant, though it's hard to see how), because every comparison-based sort provably requires $\Omega(n\log n)$ comparisons in the worst case.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29730