Re: Median: Oasis and Fast Sorting Algorithm

[Leonard Mada <discoleo gmx net>]

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