# Re: Median: Oasis and Fast Sorting Algorithm

• From: Leonard Mada <discoleo gmx net>
• To: gnumeric-list gnome org
• Subject: Re: Median: Oasis and Fast Sorting Algorithm
• Date: Sat, 10 Feb 2007 19:49:53 +0200

```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,