ちょまどさんに触発されてHaskellでいくつかのソートアルゴリズムを書いてみました。

Sort.hs

module Sort (
  bubbleSort,
  mergeSort,
  quickSort) where

import Data.List (splitAt)

bubbleSort, mergeSort, quickSort :: Ord a => [a] -> [a]

bubbleSort xs = foldr ((.) bubbleSort' . flip const) xs [0..length xs]
  where
  bubbleSort' [] = []
  bubbleSort' (x:[]) = [x]
  bubbleSort' (x:y:xs)
    |x > y' = y' : x : xs'
    |otherwise = x : y' : xs'
    where
    (y':xs') = bubbleSort' (y:xs)

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = case split xs of
  (xs', ys') -> merge (mergeSort xs') (mergeSort ys')
  where
  merge xs [] = xs
  merge[] ys = ys
  merge (x:xs) (y:ys)
    |x == y = x : y : merge xs ys
    |x < y = x : merge xs (y:ys)
    |x > y = y : merge (x:xs) ys
  split xs = splitAt (length xs `div` 2) xs

quickSort [] = []
quickSort (x:xs) = quickSort [y|y <- xs, y < x] ++ [x] ++ quickSort [z|z <- xs, x <= z]