Slow insertion sorting

Question

insertionSort :: (Ord a) => [a] -> [a]
insertionSort (x:xs) = insertionSortIter [x] xs 
    where insertionSortIter sorted []      =  sorted  
          insertionSortIter sorted (x:xs)  =  insertionSortIter (insert x sorted (length sorted)) xs
          insert x list n   --insert x in list at n
                | n == 0    = x:list
                | x < list !! (n - 1)   = insert x list (n - 1)
                | otherwise = firstns ++ (x:other) where (firstns, other) = splitAt n list
-- [1..10000] 30s                    
mergeSort :: (Ord a) => [a] -> [a]
mergeSort (x:[])      = [x]
mergeSort  list       = merge (mergeSort list1) (mergeSort list2)
        where (list1, list2) = splitAt (length list `div` 2) list
              merge [] list       = list
              merge list []       = list
              merge (x:xs) (y:ys) = if x < y then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)
-- [1..10000] 2.4s

Time of execution is specified with time of building (at 1 or 1.5s). But still you can feel the difference.

Probably the problem is execution of each branch in guard of insert function or firstns ++ (x:other) is too slow. But in any case, to put the item in the end of the list I need to go through the entire list for O(n).

Answer 1

Your insert function is slow. Here's how to do insertion sort:

insertionSort :: Ord a => [a] -> [a]
insertionSort xs = f [] xs
  where
    f rs []     = rs
    f rs (x:xs) = f (insert x rs) xs

    insert x []         = [x]
    insert x rrs@(r:rs) = if x < r then x:rrs else r:insert x rs

In case of confusion, the rrs@(r:rs) syntax means that rrs is the entire list, r is its head, and rs is its tail.

insert goes through the list and puts out all the elements that are supposed to be in front of x, then it puts out x followed by elements that are supposed to be after x.