I can wager a guess: On paper smoothsort appears to be the better sorting algorithm, with identically or better complexity then Quicksort and Mergesort in basic

I can wager a guess: On paper smoothsort appears to be the better sorting algorithm, with identically or better complexity then Quicksort and Mergesort in basically every category. In addition, smoothsort works better with data that's close to being sorted. Why then is it slower in this case, and not as widely used? Part of the reason is that smoothsort is simply not very widely known, and thus not as many people know how it works compared to Quicksort or Mergesort. Nothing that, while complexity is important to take into account and looks good on paper, complexity leaves off the 'constants', which is generally what people attribute heapsort's (And thus, smoothsort's) higher number of comparisons. All that noted, smoothsort (and heapsort) have the big advantages of being in-place (merge is not), requiring O(1) extra space in the worst case (Quicksort can require up to O(n) extra space), and has a guaranteed upper-bound of O(n lg n) in the worst case (Quicksort can degenerate to O(n^2) performance with bad data). This means that heapsort may not always outperform Quicksort, but gives better guarantees about speed and data usage then Quicksort (And much better then Mergesort, which requires a lots of extra allocated data). Smoothsort is essentially just a better heapsort which functions even better when the list is close to already sorted.