gistfile1.hs

module Main where

import Control.Monad.State
import Data.Word

type Counter = Word64
type MyState = State Counter

mergesort :: (a -> a -> Ordering) -> [a] -> MyState [a]
mergesort cmp = mergesort' cmp . map wrap

mergesort' :: (a -> a -> Ordering) -> [[a]] -> MyState [a]
mergesort' _   [] = return []
mergesort' _   [xs] = return xs
mergesort' cmp xss = do
    t <-  merge_pairs cmp xss
    mergesort' cmp t

merge_pairs :: (a -> a -> Ordering) -> [[a]] -> MyState [[a]]
merge_pairs _   [] = return []
merge_pairs _   [xs] = return [xs]
merge_pairs cmp (xs:ys:xss) = do
    h <- merge cmp xs ys
    t <- merge_pairs cmp xss
    return (h: t) 

merge :: (a -> a -> Ordering) -> [a] -> [a] -> MyState [a]
merge _  [] ys = return ys
merge _   xs [] = return xs
merge cmp (x:xs) (y:ys)
 = case x `cmp` y of
        GT -> do
              modify (+1)
              t <- merge cmp (x:xs)   ys
              return (y : t)
        _  -> do
              t <- merge cmp    xs (y:ys)
              return (x: t)

wrap :: a -> [a]
wrap x = [x]

readInt :: String -> Int
readInt = read

main :: IO()
main = do
   strs <- fmap lines $ readFile "IntegerArray.txt"  -- [1..100000] in random order
   let numbers = map readInt strs
   print $ execState (mergesort compare numbers) 0