import System.Random
import qualified Data.Sequence as S
import qualified Data.List as L
import Data.Foldable(toList)

data Tree a = Node !Int (Tree a) !Int [a] !Int (Tree a) | Leaf

sort :: (Ord a, RandomGen g) => S.Seq a -> g -> (S.Seq a, g)
sort sq g = (sq', g'')
    where
        (g',g'') = split g
        n = S.length sq
        tree = qsort (toList sq) g'
        lst = map (index tree) [0..n-1]
        sq' = S.fromList lst

qsort :: (Ord a, RandomGen g) => [a] -> g -> Tree a
qsort [] g = Leaf
qsort [x] g = Node 0 Leaf 1 [x] 0 Leaf
qsort lst g = Node (length lt) (qsort lt g1) (length eq) eq (length gt) (qsort gt g3)
    where
        n = length lst
        (i,g0) = randomR (0,n-1) g
        (g1,g3) = split g0
        (lt,eq,gt) = part lst (lst!!i)

index :: Tree a -> Int -> a
index (Node nL l nE e nR r) n
    | n < nL = l `index` n
    | n - nL < nE = head e
    | otherwise = r `index` (n - nL - nE)

part :: Ord a => [a] -> a -> ([a],[a],[a])
part lst x = L.foldl' f ([],[],[]) (reverse lst)
    where
        f (a,b,c) y = case compare y x of
                        LT -> (y:a,b,c)
                        EQ -> (a,y:b,c)
                        GT -> (a,b,y:c)