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(nlog 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(nlog n)$ comparisons in the worst case.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/29730
