Раздел «Парадигмы».SortHaskell:

Сортировка qsort и msort на Haskell


module Sort where

mergeSort [] = []
mergeSort [x] = [x]

mergeSort xs | size > 0 =
   merge (mergeSort front) (mergeSort back)
      where   
         size = length xs `div` 2
         front = take size xs
         back = drop size xs

merge :: Ord a => [a] -> [a] -> [a]
merge (x : xs) (y : ys)
   | x <= y   = x : merge xs (y : ys)
   | x > y    = y : merge (x : xs) ys
merge [] ys = ys
merge xs [] = xs




qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]

-- ArtemVoroztsov - 22 Apr 2005