Haskell MergeSort с использованием монады ST работает слишком медленно

Question

Я попытался сравнить изменяемую версию алгоритма сортировки слиянием в Haskell с неизменной версией со списками, но изменяемая версия, использующая монаду ST и STUArray, значительно медленнее. Разве неизменная природаmergesortверсия со списками увеличивает накладные расходы и должна ли быть поэтому медленнее? Если да, то почемуmergesortStработают так медленно? Это код:

import Data.List.Ordered (merge)
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
import Control.Monad.ST
import Data.Array.Base (unsafeRead, unsafeWrite)

mergesort [] = []
mergesort [x] = [x]   
mergesort xs = let m = flip div 2 . length $ xs
                in mergesort (take m xs) `merge` mergesort (drop m xs)


mergesortSt :: [Int] -> UArray Int Int
mergesortSt xs = runSTUArray $ do
                  -- mergesort version with 2 arrays (1 used as temp storage)
                  temp <- newListArray (0,length xs - 1) xs :: ST s (STUArray s Int Int)
                  arr <- newListArray (0,length xs - 1) xs :: ST s (STUArray s Int Int)
                  
                  _mergesortSt temp arr 0 (length xs)
                  return arr
                     
_mergesortSt :: STUArray s Int Int -> STUArray s Int Int -> Int -> Int -> ST s ()
_mergesortSt temp arr l r | r-l <= 0 = return ()
                          | r-l == 1 = unsafeRead temp l >>= unsafeWrite arr l
                          | otherwise = let m = (r-l) `div` 2 + l
                                          in do
                                             _mergesortSt arr temp l m
                                             _mergesortSt arr temp m r
                                             _mergeSt temp arr l r
                                             return ()

-- the elements in ranges [l..mid] and [mid..r] in temp array are sorted
-- result is: arr array in range [l..r] is sorted
-- the (l,r) tuple holds the indexes to the two sorted subarrays 
-- during the merge process. l is for the left subarray and r for the right one                               
_mergeSt :: STUArray s Int Int -> STUArray s Int Int -> Int -> Int -> ST s ()
_mergeSt temp arr ls rs = foldM foldFun (ls,mid) [ls..rs-1] >> return ()
                          where mid = (rs-ls) `div` 2 + ls
                                foldFun = (\(l,r) ind -> do
                                     if (l >= mid) then
                                        unsafeRead temp r >>= unsafeWrite arr ind >> return (l,r+1)
                                     else
                                        if r >= rs then
                                           unsafeRead temp l >>= unsafeWrite arr ind >> return (l+1,r)
                                        else do
                                           lv <- unsafeRead temp l
                                           rv <- unsafeRead temp r
                                           if (lv < rv) then
                                              unsafeWrite arr ind lv >> return (l+1,r)
                                           else
                                              unsafeWrite arr ind rv >> return (l,r+1))

Основное узкое место в функции _mergeSt, но я не знаю почему. Я читал, что упакованные массивы или writeArray/readArray влияют на производительность, но ни один из этих двух здесь не применим. Есть что-нибудь в функции foldM?