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$
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 '12 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 '12 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 '12 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 '14 at 13:53

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.