Geoff Leyland wrote:
Good question. I just tested (b) vs a pure lua binary heap and the binary heap is so much better (the sort version still hasn't finished) that I think I must have got (b) wrong
Well, not necessarily.On a queue of n items, an insertion or removal costs O(log n) (at worst) with a binary heap, O(n log n) (on average) with quicksort. O(x) roughly means "proportional to x". That makes the quicksort implementation about n times slower (x some constant value). That factor n may overhelm the advantage of quicksorting in C instead of in Lua. Also, if the quicksort is naively implemented, you may be hitting a weakness of the algorithm, such that the sorting time becomes O(n^2) instead of O(n log n) : nearly another factor n. (Someone else already pointed that out.)
Frédéric