```Clifford Heath wrote:
> Marcin Raczkowski wrote:
>> There are reaserch papers that descripbe O(nlogn) instead of (nlog^2n)
>> algorithms but They are usually full of complex math and 20-50 pages
>> long. Also one that i could understand Is based n pointers and
>> interlinked lists and it's kinda hard to implement in Ruby
>
> The wikipedia page for kdtrees references an o(n) median-finding algorithm
> in a book compiled by Cormen and others. I have the book, and the algorithm
> doesn't look too scary. I might have a go at implementing it. But in any
> case, the exact median is only needed if you demand an exactly-balanced
> tree.
> Subsequent insertions will unbalance the tree anyhow in most cases, so it's
> probably not necessary.
>
> The algorithm for finding the i'th lowest entry given in the book is as
> follows.
> (copyright, fair use provisions allow posting):
>
> The SELECT algorithm determines the ith smallest of an input array of n
>  > 1 elements by
> executing the following steps. (If n = 1, then SELECT merely returns its
> only input value as
> the ith smallest.)
> 1. Divide the n elements of the input array into n/5 groups of 5
> elements each and at
> most one group made up of the remaining n mod 5 elements.
> 2. Find the median of each of the n/5 groups by first insertion
> sorting the elements of
> each group (of which there are at most 5) and then picking the median
> from the sorted
> list of group elements.
> 3. Use SELECT recursively to find the median x of the n/5 medians
> found in step 2.
> (If there are an even number of medians, then by our convention, x is
> the lower
> median.)
> 4. Partition the input array around the median-of-medians x using the
> modified version of
> PARTITION. Let k be one more than the number of elements on the low side
> of the
> partition, so that x is the kth smallest element and there are n-k
> elements on the high
> side of the partition.
> 5. If i = k, then return x. Otherwise, use SELECT recursively to find
> the ith smallest
> element on the low side if i < k, or the (i - k)th smallest element on
> the high side if i >
> k.
>
> That's it, not too scary.
>
> Clifford Heath.
>
>

I didn't say it was scary, I'm not scared of complex math but since
finals are coming soon I don't have enought time.

I didn't have this book, and other sources were pretty confusing
(Reserch papers tend to be this way) - after i understood the algorithm
writing Ruby implementation was piece of cake

Anyway thanks for posting this piece of article, I'll try to implement
it ASAP.

about finding median - my algorithm doesn't find it either, but problem
is to find a fast way to select (with some degree of aproximation)
elements that were assigned to current branch

```