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,[x],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]