7
$\begingroup$

For a comparison based sorting algorithm, it is desirable to:

  1. Be stable
  2. Run in $O(n\ \log n)$
  3. Operate in $O(1)$ space

I can find algorithms that satisfy any two of these but I can't find any that satisfy all three. Does it exist? Is it proven not to exist?

$\endgroup$

1 Answer 1

14
$\begingroup$

Mergesort satisfies all three requirements (when merging is performed in place). See Pardo, L.T., "Stable sorting and merging with optimal space and time bounds", SIAM J. Comput. 6 (1977), 351-372.

$\endgroup$
4
  • $\begingroup$ I think that the algorithm uses $O(1)$ pointers, but has a recursive call stack that is logarithmic in the size of the list. Am I mistaken? $\endgroup$
    – aelguindy
    Apr 11, 2012 at 11:54
  • 6
    $\begingroup$ Mergesort can be implemented without recursion, essentially by doing a bottom-up level-order traversal of the recursion tree. $\endgroup$
    – Jeffε
    Apr 11, 2012 at 12:15
  • 1
    $\begingroup$ there is a nice paper by Salowe and Steiger that describes some background and gives simplified algorithms: dx.doi.org/10.1016/0196-6774(87)90050-2 $\endgroup$ Apr 13, 2012 at 15:34
  • $\begingroup$ Here is an implementation of such a sort, along with a lot of documentation of how it's implemented: github.com/BonzaiThePenguin/WikiSort/tree/master $\endgroup$ Jun 27, 2014 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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