How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?
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.
The best way to sort doubly linked lists I'm aware of is to use natural mergesort. You start by splitting the list first to sorted sublists by traversing it once and finding sorted list sequences. These sorted sublists are linked together with backward-pointers of the elements to avoid additional memory requirement during the sort. Then just repeat merging sublist pairs until there's only one list left. In the end you traverse the list once again and fix-up the backward-pointers.
This is still $O(n\log n)$ but the additional memory requirement is optimized from $O(n)$ of iterative mergesort implementation to $O(1)$. Also finding the sorted sublist at start helps with the performance if the list elements are not completely random.