-- Copyright (c) 1982-1999 Lennart Augustsson, Thomas Johnsson
-- See LICENSE for the full license.
--
module Sort(sortLe) where

sortLe :: (a -> a -> Bool) -> [a] -> [a]
sortLe le l = tmsort le l

--sort :: (Ord a) => [a] -> [a]
--sort l = tmsort (<=) l

tmsort :: (a -> a -> Bool) -> [a] -> [a]
tmsort _ [] = []
tmsort _ [x] = [x]                -- just for speed
tmsort le (x:xs) = msort le (upSeq le xs [x])

upSeq :: (a -> a -> Bool) -> [a] -> [a] -> [[a]]
upSeq _  [] xs = [reverse xs]
upSeq le (y:ys) xxs@(x:xs) =
        if le x y then
            upSeq le ys (y:xxs)
        else
            reverse xxs : upSeq le ys [y]
upSeq _ _ [] = error ("Sort.hs :: upSeq unexpected pattern" )

msort :: (a -> a -> Bool) -> [[a]] -> [a]
msort _ [xs] = xs
msort le xss = msort le (mergePairs le xss)

mergePairs :: (a -> a -> Bool) -> [[a]] -> [[a]]
mergePairs le (xs:ys:xss) = merge le xs ys : mergePairs le xss
mergePairs _  xss = xss

merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge le xxs@(x:xs) yys@(y:ys) =
        if le x y then
            x:merge le xs yys
        else
            y:merge le xxs ys
merge _  []         yys = yys
merge _  xxs        []  = xxs