Интересное.

[thesz]

import Data.Bits

qs [] = []
qs [x] = [x]
qs (x:xs) = qs (filter (< x) xs) ++ (x:filter (== x) xs) ++ qs (filter (> x) xs)

rnd :: Integer -> [Integer] -- для пущей тормознутости.
rnd range = concat $
zipWith (\x y -> [x,y]) (eachsame l) (reverse (eachsame (tail l)))
where
l = map (\x -> x `xor` shiftR x 1) $ [1..range]

eachsame (x:_:xs) = x:eachsame xs
eachsame xs = xs

Что интересно, получение первого элемента (head $ qs $ rnd N) имеет эмпирическую сложность O(N), подтверждающую теоретическую сложность этого метода.

Что на RSDN означает оценка 6/1? Или 82/5?