A very wierd sorting algorithm

Hi everyone. I am involved with alot with Wikipedia, and there is a
page over there which I cannot make heads or tails out of. For those of
you who haven't heard about wikipedia, it is an encyclopedia compiled
by it's users, ie an encyclopedia which anyone, whoever they are, can
edit. For this reason there often appear things which might be untrue
or even hoaxes. I would like some help with one of those pages.

The article in question is

http://en.wikipedia.org/wiki/Patience_sorting

It is about a sorting method called "Patience sorting", which (by it's
description) is a deterministic comparison-sort that has a worst-case
runtime of O(n log log n). Now, I am only a crappy self-taught computer
scientist, but after such a statement all sorts of warning-bells go
off. The article links to a paper (at
http://www.pims.math.ca/publications/preprints/bespamyatnikh-segal_6-12-99.ps.gz
) that provieds the details. The paper infact provides a complete
algorithm and a proof of the running-time (although the proof looks
very suspect to me, but I really don't have the expertise to properly
judge).

Can anyone please help me explain what is going on so I can fix it (or,
if you want, do it yourselfs, it is posted on wikipedia :P), or explain
if I am making incorrect assumptions.

Grateful
Oskar Sigvardsson
(Gkhan on wikipedia)

.