Sorting Algorithms

[qw]

Hi everybody,

Did you see this: http://youtu.be/kPRA0W1kECg? It's intriguing. Some I've never heard of before, like the bitonic sort. The bogo sort is painful to look at!

[bwat]

I was documenting a quantile function today and in my searches on the net came across a sorting algorithm that was completely new to me: Flashsort http://www.neubert.net/FSOIntro.html.

In the same language system that I implemented the quantile function, I have also implemented 3 different sorts: quicksort, merge sort, and topological sort. I can't see me offering any more. If the users need another algorithm, they can implement it themselves.

I reckon that 99% of the time programmers don't need anything other than your typical entry level textbook sorting algorithm and when they find themselves in the remaining 1%, a library function implementation probably won't do.

Edit: It would be interesting to know what algorithms others are using and why?

[Combuster]

Both quicksort and mergesort have additional memory requirements and therefore not really befitting a kernel. In addition, the textbook implementation of quicksort is worst case on already sorted sets. Therefore if I actually need to implement a proper sorting algorithm, it typically ends up being either shellsort or heapsort.

Sorting turns out to be much too rare in practice compared to the time school puts in it.

[AndrewAPrice]

I found merge sort to be fantastic when sorting linked lists - it doesn't require any extra memory.