import Control.Monad
import Control.Monad.ListM (sortByM, insertByM, partitionM, minimumByM)
import Data.Bool (bool)
import Data.Monoid
import Data.List


isortM, msortM, tsortM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a]


msortM = sortByM


isortM cmp = foldM (flip (insertByM cmp)) []


tsortM cmp = go
  where
    go [] = pure []
    go (h:t) = do (l, g) <- partitionM (fmap (LT /=) . cmp h) t
                  go l <+> pure [h] <+> go g
    (<+>) = liftM2 (++)