Медленная сортировка вставки

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 

Время исполнения указано со временем постройки (при 1 или 1,5 с). Но все же вы можете почувствовать разницу.

Возможно, проблема заключается в выполнении каждой ветви в защите insert или firstns ++ (x:other) слишком медленно. Но в любом случае, чтобы поместить элемент в конец списка, мне нужно пройти весь список для O (n).

Answer 1

Ваша insert функция работает медленно. Вот как это сделать вставки рода:

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 

В случае путаницы, синтаксис rrs@(r:rs) означает, что rrs является всем списком, r является его головой, и rs является его хвостом.

insert просматривает список и помещает все элементы, которые должны быть перед x, то тушит x следуют элементы, которые должны быть после x.