import Debug.Trace (trace)
quicksort4 this =
case l of
0 -> []
1 -> this
2 -> let (a:b:[]) = this
in if b > a then this else b : [a]
_ ->
let pivot = findPivot
(below, equal, above) = partitionCompare pivot
in quicksort4 below ++ equal ++ quicksort4 above
where
l = length this; m = l `div` 2
findPivot = median3 (this !! 0) (this !! m) (this !! (l - 1))
partitionCompare p = p3 ([], [], []) p this
p3 r _ [] = {- trace (show r) -} r
p3 (b, a, e) p (x:xs) =
case compare x p of
LT -> p3 (b ++ [x], a, e) p xs
EQ -> p3 (b, a ++ [x], e) p xs
GT -> p3 (b, a, e ++ [x]) p xs
median3 a b c =
case (compare a b, compare b c, compare a c) of
(LT, LT, _) -> b
(LT, GT, LT) -> c
(LT, GT, GT) -> a
(GT, LT, LT) -> a
(GT, LT, GT) -> c
(GT, GT, _) -> b
(EQ, _, _) -> a
(_, EQ, _) -> b
(_, _, EQ) -> c