Dear Uri, you are very wrong.
I made some errors, too, so I repeat the calculations: (with n elements) - initial sort: n/2 * log(n/2) - 2 comparisons per remaining elements: 2*(n/2-1) = n - 2 - search position of new element: log[(n/2-1)!] << log[(n/4)^(n/4)] = n/4 * log(n/4) - move array (with worst algorithm): log[(n/2)!] << log[(n/4)^(n/4)] = n/4 * log(n/4) -- please note, we move at most half the array, because we always have an element to the right and the left that will be deleted; so we can move without creating a new array and without allocating new memory; also, we can decide which array to move, i.e. the shorter of the left/right part; because this array is shrinking, so the penalty is log[(n/2)!] - when adding all those numbers, we end with: O(...) < n/2 * log(n/2) + n -2 + n/2 * log(n/4) = n * log(n) -2, so, even under the worst assumption, it will be less than n * log(n), and because log[(n/2-1)!] << log[(n/4)^(n/4)], there will indeed be a significant difference. I presume, that more realistically, this algorithm will be 2 times faster than the corresponding sort and uses only half the memory. Sincerely, Leonard Mada _______________________________________________ gnumeric-list mailing list gnumeric-list@gnome.org http://mail.gnome.org/mailman/listinfo/gnumeric-list
