编辑代码

module Main where
import Control.Monad.Writer


merge [] xs = xs
merge xs [] = xs
merge (x:xs) (y:ys)
  | x<=y = x:merge xs (y:ys)
  | otherwise = y:merge (x:xs) ys


indent n = showString (take (4*n) (repeat ' '))


nl = showChar '\n'


mergesort :: Int -> [Int] -> Writer String [Int]
mergesort l [] = do
  return []


mergesort l s@[x] = do
  return [x]


mergesort l s@xs = do
  tell $ (indent l.showString "mergesort:   ".shows s.showString "\n") ""
  let (a1,a2) = splitAt (length s `div` 2) xs
  curMergeResult <- liftM2 merge (mergesort (l+2) a1) (mergesort (l+2) a2)
  tell $ (indent l.showString "after merge: " .shows curMergeResult) "\n"
  return curMergeResult
  


main :: IO ()
main = do
  let res = runWriter $ mergesort 0 [11,44,23,67,88,65,34,48,12,22,34,2,1,25,34,5,76,3,4,5,22,56,84,64,56,15,35,75,33,7,92,87,65,52,7,227,62,28,29,39,45,9,12]
  putStrLn $show $ fst $res
  putStrLn $ snd $ res