バカソート

import List

divid :: [a] -> [([a], [a])]
divid xs = zip (inits xs) (tails xs)

perm :: [a] -> [[a]]
perm []         = []
perm [x]        = [[x]]
perm xs = concat $ map (\(h, t:ts) -> map (\ys -> t : ys) $ perm ( h ++ ts)) $ init $  divid xs

isSorted :: Ord a => [a] -> Bool
isSorted []         = True
isSorted [x]        = True
isSorted (x0:x1:xs) | x0 <= x1  = isSorted (x1:xs)
                    | otherwise = False

bakaSort:: Ord a => [a] -> [a]
bakaSort xs = case find isSorted $ perm xs of
              Just ys -> ys
              Nothing -> error "permSort"

> last $ perm [5,4..1]
[1,2,3,4,5]
> bakaSort [10,9..1]
[1,2,3,4,5,6,7,8,9,10]

順列組合せを作って、ソートされてる順列を見付ける (と書けば、ソートされてるのが見つかるまで順列組合せをつくるとなる)。
比較回数はリストの長さが n だと n * n!。n = 11 くらいで諦める。
# バカソートって基本挿入法のことだったきもする。