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

  • 3
    $\begingroup$ Checking any algorithms textbook or Wikipedia's articles on sorting algorithms would give you plenty of options that are faster than $O(n^2)$. So, what research did you do before you asked here? $\endgroup$ – David Richerby Sep 7 '14 at 11:57

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.

  • $\begingroup$ I recall for doubly-linked lists you can use the extra pointer storage to do the merge sort without additional storage requirements. $\endgroup$ – JarkkoL Sep 7 '14 at 16:13
  • 1
    $\begingroup$ @JarkkoL If you can recall, look up or figure out the details, that would be the basis of a good answer along the lines of "Doubly linked versus singly linked doesn't help the time complexity but it does cut the space requirement from $O(\text{something})$ to $O(\text{something else})$." $\endgroup$ – David Richerby Sep 7 '14 at 16:26
  • 1
    $\begingroup$ I wouldn't be surprised, though, if it turns out that the procedure is basically to turn the list into singly linked temporarily and use the memory cells of the backwards links for the sorting procedure. $\endgroup$ – FrankW Sep 7 '14 at 16:39
  • $\begingroup$ @David The forward pointers are used for linking the elements in sub-lists and back pointers to link the sub-lists. So you optimize the additional O(n) memory usage to O(1) $\endgroup$ – JarkkoL Sep 8 '14 at 1:27

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.

  • $\begingroup$ By the way, when using $O(\cdot)$ notation, you don't need to specify the base of the log, since $\log_a n = \log_b n / \log_b a$, i.e., they differ by a constant factor. $\endgroup$ – David Richerby Sep 8 '14 at 8:08
  • $\begingroup$ Does merge sort on singly linked lists really require $O(n)$ extra space? The recursion depth is logarithmic and each recursive call just needs a pointer to the head of each list plus some constant amount of work space so shouldn't it be $O(\log n)$ pointers? $\endgroup$ – David Richerby Sep 8 '14 at 8:12
  • $\begingroup$ No, mergesort starts by splitting the list into $2$ sublists, each of length $n/2$. $\endgroup$ – David Richerby Sep 8 '14 at 12:41
  • $\begingroup$ That's an implementation detail. You can implement mergesort recursively or iteratively which both have their pros and cons. I'm in the favour of iterative implementation due to performance, where you split the list to n/2 sublists $\endgroup$ – JarkkoL Sep 8 '14 at 12:49
  • $\begingroup$ It's not an implementation detail -- it's the definition of the algorithm! Furthermore, it directly affects the space complexity, since your way (splitting into $n/2$ lists, each of length two) requires $\Theta(n)$ extra storage, whereas the standard way (splitting into two lists, each of length $n/2$) only requires $O(\log n)$ storage. Besides, the whole question is about implementation details: about whether you choose to implement your lists with single or double links. $\endgroup$ – David Richerby Sep 8 '14 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.