<p>Having just done some reading up on the two algorithms, it would appear that heapsort has no implicit <em>O</em> 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.</p>

<p>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.</p>

<p>Indeed, the only real accessible literature is this <a href="http://www.keithschwarz.com/smoothsort/" rel="nofollow">write-up</a> by Keith Schwarz. It is also the basis of the <a href="http://en.wikipedia.org/wiki/Smoothsort" rel="nofollow">wikipedia article</a>.</p>

CC BY-SA 3.0
2011-10-06T19:49:09.970Z
2012-06-24T21:22:39.430Z
2012-06-24T21:22:39.430Z
Paul Wagland
<p><a href="http://en.wikipedia.org/wiki/Smoothsort" rel="nofollow">Wikipedia</a> states that the advantages of smoothsort over heapsort is that <em>at times</em> it comes closer to O(n) time.</p>

<p>Now I was wondering what advantage does heapsort has over smoothsort?</p>

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

CC BY-SA 3.0
2011-10-05T12:36:35.780Z
Have you compared implementations? Perhaps the difference is that smoothsort has a larger overhead both in terms of execution time and memory used.
Dave Clarke
CC BY-SA 3.0
2011-10-05T17:29:17.583Z
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.
Peter Shor 
CC BY-SA 3.0
2011-10-06T07:53:29.697Z
@DaveClarke I mean not in the implementation (which can vary) but in the algorithm itself
Pacerier
CC BY-SA 3.0
2011-10-08T21:17:52.163Z
@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?
Paul Wagland
CC BY-SA 3.0
2011-10-08T21:40:57.267Z
@Paul: I'm not sure, but it looked like it when I was briefly looking at the algorithm. However, that's a worst-case behavior; it would only take O(n) time if the input is already nearly sorted.
Peter Shor 
CC BY-SA 3.0
2011-10-10T14:34:17.200Z
Let me explain my reasoning in a little more detail. A brief glance at the algorithm made it look like adding a key to the heap in smoothsort took O(log n) comparisons on average. For heapsort, there is a clever way to build the heap in O(n) comparisons. If this is true for smoothsort as well, then the O(n log n) comparisons that you use in building the heap are in some sense wasted, since the optimal smoothsort algorithm doesn't use them. Since I expect the optimal smoothsort and the optimal heapsort algorithms to be roughly comparable, this would put smoothsort at a disadvantage.
Peter Shor 
CC BY-SA 3.0
2015-12-02T13:16:23.163Z
@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).
ScootyPuff
<ds.algorithms><sorting>
what advantage does heapsort has over smoothsort?
Pacerier
# what advantage does heapsort has over smoothsort?

(Asked by: username_0 on 2011-10-05)

[Wikipedia](http://en.wikipedia.org/wiki/Smoothsort) 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) ?

**Tags:** ds.algorithms, sorting
> **Comments:**
> **username_1**: Have you compared implementations? Perhaps the difference is that smoothsort has a larger overhead both in terms of execution time and memory used.  
> **username_2**: 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.  
> **username_0**: @DaveClarke I mean not in the implementation (which can vary) but in the algorithm itself  
> **username_3**: @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?  
> **username_2**: @Paul: I'm not sure, but it looked like it when I was briefly looking at the algorithm. However, that's a worst-case behavior; it would only take O(n) time if the input is already nearly sorted.  
> **username_2**: Let me explain my reasoning in a little more detail. A brief glance at the algorithm made it look like adding a key to the heap in smoothsort took O(log n) comparisons on average. For heapsort, there is a clever way to build the heap in O(n) comparisons. If this is true for smoothsort as well, then the O(n log n) comparisons that you use in building the heap are in some sense wasted, since the optimal smoothsort algorithm doesn't use them. Since I expect the optimal smoothsort and the optimal heapsort algorithms to be roughly comparable, this would put smoothsort at a disadvantage.  
> **username_4**: @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).  

---

## 1 answers

### Answer by username_3 on 2011-10-06. Score: 10 | Accepted answer

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](http://www.keithschwarz.com/smoothsort/) by Keith Schwarz. It is also the basis of the [wikipedia article](http://en.wikipedia.org/wiki/Smoothsort).


---

