dc :: (a -> Bool) -> (a -> [a]) -> (a -> b) -> (b -> b -> b) -> a -> b
-- [a] non-empty!
dc trivial divide solve combine problem
| trivial problem = solve problem
| otherwise = foldr1 combine $ map conquer $ divide problem
where
conquer = dc trivial divide solve combine
quickSort :: Ord a => [a] -> [a]
quickSort = dc trivial split id (++)
where
trivial xs = null xs || null (tail xs)
split (x:xs) = [filter (=x) xs]
quickSortTest = quickSortTest1 && quickSortTest2
quickSortTest1 = quickSort [1,0,-2,-1] == [-2,-1,0,1]
quickSortTest2 = quickSort [1,0,-1,-1] == [-1,-1,0,1]