sortby f []  = []
sortby f [x] = [x]
sortby f (x : y : xs) = mergeby f (cross (sortby f, sortby f) (divide (x : y : xs)))

-- Eine Liste in zwei Teillisten zerlegen (abwechselnd auf zwei Listen verteilen, bis die leere Liste erreicht ist)
divide :: [a] -> ([a],[a])
divide = foldr allocate ([],[]) 
         where allocate x (ys,zs) = (zs,x:ys)

-- Zwei Listen mischen, bis eine Liste leer ist
mergeby :: Ord b => (a -> b) -> ([a],[a]) -> [a]
mergeby f ([],ys)   = ys
mergeby f (x:xs,[]) = x:xs
mergeby f (x:xs,y:ys)
 | f x <= f y = x : mergeby f (xs,y:ys)
 | otherwise  = y : mergeby f (x:xs,ys)