37
$\begingroup$

I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources?

Just a reminder, in place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space. Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.

For example, naive merge sort is worst case $O(n \ln n)$ and stable but uses $O(n)$ extra space. Standard quicksort can be made stable, is in place but is worst case $O(n^2)$. Heapsort is in place, worst case $O(n \ln n)$ but isn't stable. Wikipedia has a nice chart of which sorting algorithms have which drawbacks. Notice that there is no sorting algorithm that they list that has all three conditions of stability, worst case $O(n \ln n)$ and being in place.

I have found a paper called "Practical in-place mergesort" by Katajainen, Pasanen and Teuhola, which claims to have a worst case $O(n \ln n)$ in place stable mergesort variant. If I understand their results correctly, they use (bottom-up?) mergesort recursively on the first $\frac{1}{4}$ of the array and the latter $\frac{1}{2}$ of the array and use the second $\frac{1}{4}$ as scratch space to do the merge. I'm still reading through this so any more information on whether I'm interpreting their results correctly is appreciated.

I would also be very interested in a worst case $O(n \ln n)$ in place stable quicksort. From what I understand, modifying quicksort to be worst case $O(n \ln n)$ requires selecting a proper pivot which would destroy the stability that it would otherwise normally enjoy.

This is purely of theoretical interest and I have no practical application. I would just like to know the algorithm that has all three of these features.

$\endgroup$
  • $\begingroup$ There is a similar question on SO here with an answer that gives the reference I provided in the question. I believe this is not a duplicate question as I'm asking for further clarification, more literature, and, with any luck, a description of the algorithm. $\endgroup$ – user834 Jul 1 '12 at 19:06
  • 1
    $\begingroup$ See this question on math.stackexchange.com. $\endgroup$ – Tsuyoshi Ito Jul 1 '12 at 20:59
  • $\begingroup$ Why would different way of selecting a pivot in QuickSort destroy its stability? $\endgroup$ – svick Jul 2 '12 at 13:31
  • $\begingroup$ @svick, the only way I know how to make QuickSort worst case $O(n \ln n)$ is to choose the pivot more intelligently than random. The way that I learned to do that was by using the selection algorithm, which uses the median-of-medians algorithm, which destroys stability. If I missed something, please let me know. $\endgroup$ – user834 Jul 2 '12 at 13:34
  • $\begingroup$ @TsuyoshiIto, consider making this an answer. Also, if you could give a brief sketch of the algorithm, I think that would really be helpful as well. $\endgroup$ – user834 Jul 2 '12 at 19:55
7
$\begingroup$

There are several algorithms that are all of the above, and pretty much all of them have been invented in the last 30 years.

Probably the nicest is the class of algorithms called Block sort, including the version (called WikiSort) by Kim and Kutzner in 2008. It is not only stable and completely in-place (O(1) memory overhead in the transdichotomous model), it is also adaptive, and thus will take fewer steps to sort nearly sorted lists, converging to O(n) comparisons in the case of an already sorted list. You can find an implementation in C, C++, and Java here: https://github.com/BonzaiThePenguin/WikiSort

Also of interest is the GrailSort algorithm (also a Block sort) by Huang and Langston (1989-1992), which actually outperforms WikiSort on several types of test cases. A C++ implementation is available here: https://github.com/Mrrl/GrailSort

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

You can write an in-place, stable mergesort. See this for details. In the author's own words:

A beautiful in place - merge algorithm. Test it on inverted arrays to understand how rotations work. Fastest known in place stable sort. No risk of exploding a stack. Cost: a relatively high number of moves. Stack can still be expensive too. This is a merge sort with a smart in place merge that 'rotates' the sub arrays. This code is litteraly copied from the C++ stl library and translated in Java.

I won't copy the code here, but you can find it at the link or by checking the C++ STL. Please let me know if you would like me to try to provide a more detailed description of what's going on here.

| cite | improve this answer | |
$\endgroup$
  • 8
    $\begingroup$ If you could give a brief description, I think that would be very helpful. Also, though it might not be necessary, the referenced implementation is using recursion which adds another $O(\ln n)$ factor on space, which violates the $O(1)$ space condition (assuming we get $O(\ln n)$ bit variables for free). Perhaps the referenced algorithm can be made iterative but I'm having trouble understanding what's going on. Do you have a reference paper that the implementation is using? $\endgroup$ – user834 Jul 1 '12 at 16:13
  • $\begingroup$ Knuth addresses this in TAoCP as well. $\endgroup$ – Raphael Jul 23 '16 at 13:25
  • $\begingroup$ The algorithm you cite here is worst case $O(n\ln^2n)$. Cf. cplusplus.com/reference/algorithm/stable_sort (in particular the commentary about running time when not enough extra memory is available). $\endgroup$ – quintopia Mar 8 '17 at 6:27
1
$\begingroup$

Please take this as a long comment on some practical thoughts. Although this is not an answer to your question, I think you might be interested in this Python discussion:

This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than $\lg(N!)$ comparisons needed, and as few as $N-1$), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

[...]

Merging adjacent runs of lengths A and B in-place is very difficult. Theoretical constructions are known that can do it, but they're too difficult and slow for practical use. But if we have temp memory equal to min(A, B), it's easy.

Source: bugs.python.org, author: Tim Peters

So it seems as if Timsort still has advantages over an stable, in-place, $\mathcal{O}(n \log n)$ worst-case time complexity merge sort.

Also note that Timsort performs good on already-sorted arrays.

So Python makes use of Timsort (which is Mergesort with some tweaks) and as I've looked up the Java implementation some years ago, it was also Mergesort (I think they now also use Timsort).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Any unstable sorting algorithm can be made stable, by adding the original relative positions of the objects being compared as a tie-breaker in the comparison function. This can be done without any extra memory if you are already sorting array indices, as a way to avoid moving the actual objects around; otherwise it's an O(n) extra memory technique.

If this technique is applicable, then you can use it with heapsort to get a stable O(n log n) in-place sort for free.

Quicksort is a funny algorithm whose average case runtime is O(n log n), but whose worst case runtime is governed by some rare pathological conditions which can effectively reduce it to an inefficient insertion sort with O(n^2) runtime. A valid way to evade those pathological cases (especially those which might be deliberately constructed by an adversary) is to choose the pivots using a good randomiser, eg. a decent PRNG seeded using some true RNG, which makes the probability of experiencing the pathological behaviour infinitesimally small. Then, to avoid the PRNG dominating performance, switch to insertion sort for small divisions of the array (traditionally, 16 elements or less).

As noted by previous answers, quicksort is available in a stable-sorting variant. This does not depend on details of choosing the pivot, so the above random pivot technique remains applicable. Since insertion sort is also stable, this optimisation can also be used.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The question asks about in-place sorts. "In place" usually means that we're not sorting array indices and we can't afford $O(n)$ extra memory. $\endgroup$ – D.W. Mar 23 at 19:16
  • $\begingroup$ @D.W. That may be true theoretically, but I think these suggestions are still useful from an engineering standpoint, which is where I usually operate. On that note, radix sorting is another useful technique with O(N*m) complexity where N is number of objects and m is length of keys; this is effectively O(n) in the size of the data being sorted. And it is stable, and in-place. $\endgroup$ – Chromatix Mar 24 at 6:26
  • $\begingroup$ -1, This answer fails to understand the question. "In place" means precisely not adding more space to the passed in array. Adding index information adds an extra O(n) space which violates both the "in place" criteria and the constant extra space criteria. Quicksort is worst case O(n^2) which violates the O(n lg n) criteria in the question. This question isn't about engineering compromises, discussions of which can be found at length elsewhere. The first sentence of your answer might be a valid answer but you provide no algorithm or references so I doubt it's true. $\endgroup$ – user834 May 23 at 13:05

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.