Haskell implementation of GroupSort

groupsort.hs

module GroupSort (
    groupsort
) where

groupsort :: Ord a => [a] -> [a]
groupsort [] = []
groupsort xs = let
    groups = group xs
    n = length xs
    k = length groups
    in sort n k groups
        where
            sort 0 _ _ = []
            sort _ 1 _ = xs
            sort n k groups
                | n == k    = reverse xs
                | otherwise = foldl1 integrate groups

integrate :: Ord a => [a] -> [a] -> [a]
integrate xs [] = xs
integrate [] ys = ys
integrate xs@(x:xs') ys@(y:ys')
    | x < y     = x:integrate xs' ys
    | otherwise = y:integrate xs ys'

insert :: Ord a => a -> [[a]] -> [[a]]
insert y [] = [[y]]
insert y groups@(open@(switch:_):closed)
    | switch >= y = (y:open):closed
    | otherwise  = [y]:groups

group :: Ord a => [a] -> [[a]]
group = foldr insert []