Store the equal bucket at each internal node:The representation invariant for a tree produced by
data Tree a = Empty | Node (Tree a) [a] (Tree a)
toTree :: Ord a => [a] -> Tree a
toTree [] = Empty
toTree (pivot:xs) =
let (lo,eq,hi) = partition3 pivot xs
in Node (toTree lo) (pivot:eq) (toTree hi)
fromTree :: Tree a -> [a]
fromTree Empty = []
fromTree (Node left equal right) =
fromTree left ++ equal ++ fromTree righttoTree is that its bucket is nonempty and contains equal keys, every left-subtree key is smaller, and every right-subtree key is larger. Its multiplicities are preserved. Substituting the two equations for toTree into fromTree gives exactly the two defining equations for sort; induction proves sort = fromTree . toTree on finite inputs.Both versions call the same partition helper on the same pivot and sublists. The flattening stage makes no key comparisons. Thus fully producing the answer makes the same comparison decisions as the direct algorithm; no additional comparison against stored tree keys is introduced.
Articles by others on the same topic
There are currently no matching articles.