bearophile wrote:
Andrei Alexandrescu:
Your handwaving ain't much better than my memory. Hey, either somebody goes
through the math over here or we can give up on the whole thing and use O(n)
storage for the blessed thing.<
We can implement both, and we can look what's better in practical situations.
Agreed. Worst-case quadratic can perform much better in many
circumstances, and the proposed algorithm is tunable.
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.
Bye,
bearophile
