I'm working on a task from the one of Coursera programming courses. The purpose is to estimate the amount of inversions that are required to sort the array of numbers.
Also I'm trying to learn some Haskell basics, here is my solution:
fsthalf :: [a] -> [a] fsthalf xs = take (length xs `div` 2) xs sndhalf :: [a] -> [a] sndhalf xs = drop (length xs `div` 2) xs union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int) union (a, ac) (b, bc) = (a++b, ac+bc) merge :: ([Int], Int) -> ([Int], Int) -> ([Int], Int) merge (, ac) (bs, bc) = (bs, ac + bc) merge (as, ac) (, bc) = (as, ac + bc) merge (a:as, ac) (b:bs, bc) | a <= b = ([a], 0) `union` merge (as, ac) (b:bs, bc) | otherwise = ([b], length(a:as)) `union` merge (a:as, ac) (bs, bc) mergeSort :: ([Int], Int) -> ([Int], Int) mergeSort (s, c) | length s `elem` [0, 1] = (s, c) | otherwise = merge (mergeSort (fsthalf s, c)) (mergeSort (sndhalf s, c)) main :: IO() main = do _ <- readLn :: IO Int rawValues <- getLine let intValues = map read $ words rawValues :: [Int] print $ snd $ mergeSort (intValues, 0)
It seems to work properly, but exceeds time limits. It takes from 9 to 10 seconds to sort the longest possible list of integers (100000 values), while the limit is 6 seconds. Could anyone please point out some possible optimizations for this solution.