Quote:ThatDonGuyThe 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.

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.

Quote:kuroshivoWell, 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.

Bin sort would be even faster for this problem. Just create an incidence array of size 10 and count how many of each digit. It works for arbitrarily long sequences, whereas the prime algorithm will quickly exceed the max data size. Heap sort is O(n log n). Bin sort is O(n).Quote:ThatDonGuyThe use of heap sort in the title leads me to ask: is heap sort still the fastest method? 40 years ago, it was, but I have done some comparisons since then, and I have found that, with the vast increases in processing speed, quicksort seems to be faster now. (Well, what I call "quicksort-N", where N is usually 8 or 9; if there are N or more values in the current comparison, do a quicksort, but if there are fewer, do a "wimpysort" like bubble or shaker.)