Re: Median: Oasis and Fast Sorting Algorithm

• From: "Uri David Akavia" <uridavid akavia gmail com>
• To: "Leonard Mada" <discoleo gmx net>
• Cc: gnumeric-list gnome org
• Subject: Re: Median: Oasis and Fast Sorting Algorithm
• Date: Sat, 10 Feb 2007 18:59:09 +0200

```Right, maybe my explanation was unclear. I'll try to repeat (and ask
other people to check my math).

On 2/10/07, Leonard Mada <discoleo gmx net> wrote:
```
```
So, even in the worst scenario, this algorithm should work faster than
n* log(n). Also, (n/2 -1)! is worst case, when all residual elements
would fall inside the sorted array, so we can NOT drop them. So,
```
```No, log((n/2 -1)!) is the worst case for finding where to insert the
elements. It is not the cost of actually inserting them.

In order to insert an element into the middle of a N-sized array, you
must move N/2 elements. Are you assuming that moving N/2 elements can
be done at the same cost of moving 1 element?
This might be possible, but it means you need another N-sized array as filler.

T(n) <
```
```O(n log(n)), even IF I penalize for inserting one value into the sorted
array as there would be maximum n/2 inserts and that should cancel out
with (-n/2) [or add another n/2].
```
```Again, assuming that you can shift N elements of an array with a cost
of 1. Are you convinced it can be done?

Also note, that as x[0] and x[last]
```
```are dropped, some of the new x[i] will be either < x[1], so replacing
x[0] (NO or minimal cost) or > x[last -1], so replacing x[last], without
cost.
```
```Wrong assumption - when assuming worst case, you assume never to  gain
from actions that cost less then your worst case.

```
```Because the insert would mean
moving a contiguous memory segment (NO need to create new array, because
array is shrinking: insert 1, drop another 2 => array still shrink by
one), this operation would be very fast.
```
```Yeah, your basic assumption is that moving a contiguous memory segment
takes a cost of 1. If it takes a cost related to the size of the
memory (N), then the continuous movements need O(N*N).

Yours,

Uri David

```