Optimization suggestions

Optimization suggestions

Here is a haskell code which calculates number of swaps done in insertion
sorting. It is supposed to be O(n*log n). But it is too slow, even for
input range of ~40000 it takes more than 15 seconds to give the answer
whereas sorting the same input takes much less time (around 0.4 seconds).
I would have expected a slowdown due to all the Map operations but never
this order of magnitude.
import Data.List (sort,foldl')
import Data.Map (Map)
import qualified Data.Map as M
greaterThan :: Int -> Map Int Int -> Int
greaterThan k = M.fold (+) 0 . snd . M.split k
swaps :: [Int] -> Int
swaps = fst . foldl' with (0,M.empty)
where
with (s,m) v = (s + greaterThan v m, m')
where
m' = M.alter f v m
f Nothing = Just 1
f (Just c) = Just $ c + 1