kuroshivo
Joined: Jun 8, 2019
• Posts: 11
May 14th, 2021 at 7:49:43 AM permalink
Quote: ThatDonGuy

The use of heap sort in the title leads me to ask: is heap sort still the fastest method?

Well, after reading Donald Knuth's "The Art of Computer Programming" volume 3 on sorting and searching (more than 10 years ago) I have the feeling that there is no one-size-fits-all answer. I think there are some shallow discussions on Wikipedia, but the actual meat is in Knuth's TAOCP.
EdCollins
Joined: Oct 21, 2011
• Posts: 1553
May 14th, 2021 at 8:39:17 AM permalink
I remember, a bit more than 22 years ago, I first became absolutely fascinated by all of the different sorting algorithms that were available. Heap Sort, Insertion Sort, Bubble Sort, Quicksort, Shell Sort, Merge Sort, etc., etc., etc.

There are many different websites that help to visualize how each algorithm works. Here's just one of many:

https://www.toptal.com/developers/sorting-algorithms

And yes, there is no one size fits all answer as to which algorithm is best/fastest. A lot of it has to do with what your data looks like before it is sorted. Is it completely random? Is it nearly sorted already? Is it completely reversed? Etc.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5369
May 14th, 2021 at 10:07:42 AM permalink
Quote: kuroshivo

Well, after reading Donald Knuth's "The Art of Computer Programming" volume 3 on sorting and searching (more than 10 years ago) I have the feeling that there is no one-size-fits-all answer. I think there are some shallow discussions on Wikipedia, but the actual meat is in Knuth's TAOCP.

Speaking of Knuth, Volume 4a has a few pages on generating permutations, which was the original question in this post - so of course it's back at my office while I have been teleworking for over a year now.
teliot
Joined: Oct 19, 2009