Seminar: mergesort

• Schreiben Sie in die Datei MS.hs

  split :: [a] -> ([a], [a])
  split [] = ( [], [] )
  split (x : xs) = 
      let (ys, zs) = split xs 
      in  (x : zs, ys)
  

  und rufen Sie dann diese Funktion auf

• Vervollständigen und testen Sie die Funktion zum Zusammenfügen von bereits geordneten Listen:

  merge :: Ord a => [a] -> [a] -> [a]
  merge xs [] = xs
  merge [] ys = ys
  merge (x : xs) (y : ys) = 
      if x < y then x : merge xs (y : ys)
               else ...
  

• Dann die eigentliche Funktion zum Sortieren:

  msort :: Ord a => [a] -> [a]
  msort [] = []
  msort [x] = [x]
  msort xs = let (ys, zs) = split xs
             in  merge ( ... ) ( ... )
  

  Sortieren Sie damit eine Liste von Zahlen

• und dann die Wörter aus einer Datei:

  (hugs-prompt:) do cs <- readFile "MS.hs" ; print $ msort $ words cs