CODEWITHSUNDEEP
haskellmergesortinsertion-sort
vlastachu
vlastachu

Reputation: 257

Slow insertion sorting

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).

Upvotes: 1

Views: 372

Answers (1)

Olathe
Olathe

Reputation: 1895

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.

Upvotes: 2

Related Questions