inversions_nlogn_vs_n2.hs

-- | Main entry point to the application.
module Main where
import Debug.Trace
import System.IO


-- split inversions
invSplit':: (Ord a) => Int -> [a] -> [a] -> ([a], Int)
invSplit' i xs [] = (xs, i)
invSplit' i [] ys = (ys, i)
invSplit' i f@(x:xs) s@(y:ys)
    | x > y =
        let (sorted, ni) = invSplit' (i + (length f)) f ys in (y: sorted, ni)
    | x <= y =
        let (sorted, ni) = invSplit' i xs s in (x: sorted, ni)



inv:: (Ord a) => [a] -> ([a], Int)
inv [x] = ([x], 0)
inv lst = 
    (splitLst, splitCount + firstCount + lastCount)
    where
        (sortedFirst, firstCount) = inv first
        (sortedLast, lastCount) = inv last
        (splitLst, splitCount) = invSplit' 0 sortedFirst sortedLast
        (first, last) = splitAt (quot (length lst) 2) lst


bruteForce :: [ Int ] -> Int
bruteForce [] = 0
bruteForce [_] = 0
bruteForce ( x : xs ) = ( length . filter ( x > ) $ xs ) + bruteForce xs


readInt :: String -> Int
readInt = read

getIntArray :: String -> [Int]
getIntArray c = map readInt . words $ c


-- | The main entry point.
main :: IO ()
main = do
    contents <- readFile "IntegerArray.txt"
    print . snd . inv . getIntArray $ contents
    -- print . bruteForce . getIntArray $ contents