Re: Median: Oasis and Fast Sorting Algorithm

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.


Leonard Mada

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]