inversions_modified.hs

import Control.Monad
import Data.Vector hiding (map)
import Prelude hiding (head, tail, length, splitAt)
import System.IO

inversions :: Vector Int -> Int
inversions = snd . countInversions

countInversions :: Vector Int -> (Vector Int, Int)
countInversions xs
        | length xs <= 1 = (xs, 0)
        | otherwise      = let mid   = (length xs) `div` 2
                               (left, right) = splitAt mid xs
                               (left'  , l) = countInversions $! left
                               (right' , r) = countInversions $! right
                               (whole  , w) = id $! countSplit left' right'
                            in (whole, l + r + w)

countSplit :: Vector Int-> Vector Int -> (Vector Int, Int)
countSplit xs ys
        | length xs == 0 = (ys, 0)
        | length ys == 0 = (xs, 0)
        | x <= y    = (cons x left , l)
        | otherwise = (cons y right, r + length xs)
            where (left, l)  = countSplit (tail xs) ys
                  (right, r) = countSplit xs (tail ys) 
                  x     = head xs
                  y     = head ys

main = do
    withFile "IntegerArray.txt" ReadMode $ \h -> liftM (fromList . map (read :: String -> Int) . lines) (hGetContents h) >>= (print . inversions)