Melsort.hs

module Melsort (melsort) where

-- TODO: Linked lists are not the best for this algorithm performance-wise.
-- Consider a different structure, perhaps Vector.

-- TODO: Some preconditions are required.
push :: Ord a => a -> [[a]] -> [[a]]
push x [] = [[x]]
push x ([y]:ls) -- TODO: Is it possible that ls /= [] here? It's not.
    | x <= y = [x, y   ] : ls
    | x >  y = [   y, x] : ls
push x ([y, z]:ls)
    | x <= y    = [x, y, z   ] : ls
    | x >= z    = [   y, z, x] : ls
    | otherwise = [   y, z   ] : push x ls
push x (l:ls)
    | x <= head l =      (x:l) : ls
    | x >= last l = (l ++ [x]) : ls
    | otherwise   =          l : push x ls

-- TODO: Some preconditions are required.
merge :: Ord a => [[a]] -> [a]
merge = foldr merge' []
    where
        merge' xs     []     = xs
        merge' (x:xs) (y:ys)
            | x <= y         = x : merge' xs     (y:ys)
            | otherwise      = y : merge' (x:xs) ys

melsort :: Ord a => [a] -> [a]
melsort = merge . foldr push []