diff-tree sort

diffsort.hs

{- 
DIFF-TREE SORT

I did this as a learning exercise. 
I assume it has been discovered before.
It is an attempted optimisation of tree sort.

It uses a naive binary tree,
but each node keeps a list of same-values, 
and difference lists
are used for more efficient appending
when collapsing the tree back into a list.

Its execution time when sorting 10000 random integers
is better than that of merge sort but slightly worse
than that of quicksort or haskell's default sort.

I'll try to improve it further by
use of a better tree structure and a tighter
suturing of difference lists and trees.
-}

import Data.Monoid

newtype Diff a = Diff { getDiff :: [a] -> [a] }

toDiff :: [a] -> Diff a
toDiff xs = Diff (xs ++)

fromDiff :: Diff a -> [a]
fromDiff (Diff f) = f []

instance Monoid (Diff a) where
         mempty = Diff ([] ++)
         Diff f `mappend` Diff g = Diff (f . g)

data Ord a => Ctree a = Node [a] (Ctree a) (Ctree a) | Leaf deriving Show

cInsert :: Ord a => a -> Ctree a -> Ctree a
cInsert x Leaf = Node [x] Leaf Leaf
cInsert x (Node val@(v:vs) left right) 
       | x < v     = Node val (cInsert x left) right
       | x > v     = Node val left (cInsert x right)
       | otherwise = Node (x:v:vs) left right

toCtree :: Ord a => [a] -> Ctree a
toCtree = foldr cInsert Leaf 

diffFromCtree :: Ord a => Ctree a -> Diff a
diffFromCtree Leaf = mempty
diffFromCtree (Node v left right) = diffFromCtree left `mappend`
                                    toDiff v `mappend`
                                    diffFromCtree right

-- The final list-sorting function:
cSort :: Ord a => [a] -> [a]
cSort xs = fromDiff $ diffFromCtree $ toCtree xs