Christopher Wright: > Agreed. Worst-case quadratic can perform much better in many > circumstances, and the proposed algorithm is tunable.
I think it's not quadratic :-) (See the answer by Bill B.) > Or as an alternative, when you have hit (say) half the elements, you > copy over the remaining elements and repeat. This gives you an amortized > O(n log n) algorithm, with O(n log n) allocated memory. There are some variants of that algorithm designed to be recursive, like you say. I have tried them, and they are slower, etc. That's why I have shown here the simpler version. Sometimes more complex algorithms aren't better. Bye, bearophile
