Wikipedia states that the advantages of smoothsort over heapsort is that at times it comes closer to O(n) time.

Now I was wondering what advantage does heapsort has over smoothsort?

Or to rephrase this question, is smoothsort always a better choice than heapsort (even if the input is not already sorted to any degree) ?

  • $\begingroup$ Have you compared implementations? Perhaps the difference is that smoothsort has a larger overhead both in terms of execution time and memory used. $\endgroup$ – Dave Clarke Oct 5 '11 at 12:36
  • 8
    $\begingroup$ In heapsort, you can build the heap in time O(n), while in smoothsort, it takes time O(n log n) to build the heap. This suggests (but doesn't imply) that the time to sort random input might be longer for smoothsort. $\endgroup$ – Peter Shor Oct 5 '11 at 17:29
  • $\begingroup$ @DaveClarke I mean not in the implementation (which can vary) but in the algorithm itself $\endgroup$ – Pacerier Oct 6 '11 at 7:53
  • $\begingroup$ @PeterShor Are you sure that it takes O(n log n) to build the heap in smoothsort? That would seem to fly in the face of the claim that smoothsort is O(n) when the input is already sorted? $\endgroup$ – Paul Wagland Oct 8 '11 at 21:17
  • 1
    $\begingroup$ @PeterShor: A variant of smoothsort that uses a skew binary list as the forest of heaps can be heapified in O(n) time. To do this, convert the length of the input to skew binary (O(log(n)). The bits of this number tell you the heap sizes in the forest. Pretend such a forest already exists not already having the heap property. Enforce it. This is similar to in heapsort pretending you already have a heap without the heap property. However, even with this change, smoothsort (using skew binary) is only faster than heapsort for 10% or less unsorted (using inversions to unsort). $\endgroup$ – ScootyPuff Dec 2 '15 at 13:16

Having just done some reading up on the two algorithms, it would appear that heapsort has no implicit O advantage over smoothsort. This kind of makes sense when you think that smoothsort is just a special kind of heapsort, using a special kind of heap.

Where heapsort does have is an advantage is that it is easier to understand, and much better documented. There are very few publicly available implementations of smoothsort, and very little literature on them, however there is a lot of literature on heapsort.

Indeed, the only real accessible literature is this write-up by Keith Schwarz. It is also the basis of the wikipedia article.


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.