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
0 comments:
Post a Comment
Let us know your responses and feedback