freenode/#sicl - IRC Chatlog
Search
13:35:09
beach
Not really. I would generate random permutations and compute some statistics like average, best, worst, standard deviation.
14:03:27
pfdietz
Some sorting algorithms do well on random permutations, but poorly on (for example) almost-ordered inputs. quicksort, for example.
14:05:49
jcowan
hence introsort, a very fine variant of quicksort with guaranteed O(n log n) behavior.
16:39:28
beach
jcowan: Though if shka__ is doing what I think he is, then the purpose is to implement a very efficient stable sort for vectors. Merge sort is known to be be stable and very efficient, but the standard description of it requires O(n) extra space.
16:40:08
beach
jcowan: But there are some recent articles on how to implement merging, and therefor merge sort, in O(1) additional space.
16:42:05
beach
jcowan: I would personally like to attempt the trick we did in our article on how to process lists from the end, i.e. use SOME stack space if it is available. Then I believe one could achieve a very fast merge sort on vectors with a performance that degrades smoothly when stack space is scarce.