# Re: Median: Oasis and Fast Sorting Algorithm

• From: "Andreas J. Guelzow" <aguelzow taliesin ca>
• To: gnumeric-list gnome org
• Subject: Re: Median: Oasis and Fast Sorting Algorithm
• Date: Sat, 10 Feb 2007 11:03:14 -0700

```On Sat, 2007-10-02 at 19:49 +0200, Leonard Mada wrote:

```
```- move array (with worst algorithm): log[(n/2)!] << log[(n/4)^(n/4)] =
n/4 * log(n/4)
```
```
for n=100    log[(n/2)!]    > 140
but n/4 * log(n/4) <  81

What exactly is << supposed to mean?

```
```
so, even under the worst assumption, it will be less than n * log(n),
```
```
assuming this is true

```
```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.
```
```
"2 times faster" means nothing. You are counting artifical actions
assuming that a comparison is the same as moving a memory block. When
you write the real code a small constant factor can easily disappear.
And typically with complex algorithms it will disappear.

Andreas
--
Prof. Dr. Andreas J. Guelzow
Dept. of Mathematical & Computing Sciences
Concordia University College of Alberta

```