Inversions.hs

-- Exercise 2-2 d) in "Introduction to Algorithms" (3rd edition)

module Main where

import Test.QuickCheck
import Data.List (sort)

split :: [a] -> ([a], [a])
split as = splitAt (length as `div` 2) as

mergeWithInversions :: Ord a => [a] -> [a] -> (Int, [a])
mergeWithInversions [] bs = (0, bs)
mergeWithInversions as [] = (0, as)
mergeWithInversions (a:as) (b:bs) | a > b = let (n, rest) = mergeWithInversions (a:as) bs
                                            in (n + length as + 1, b:rest)
                                  | True  = let (n, rest) = mergeWithInversions as (b:bs)
                                            in (n, a:rest)

mergeSortWithInversions :: Ord a => [a] -> (Int, [a])
mergeSortWithInversions [] = (0, [])
mergeSortWithInversions [a] = (0, [a])
mergeSortWithInversions as = (leftInversions + rightInversions + mergeInversions, sorted)
  where (left, right)                  = split as
        (leftInversions, leftSorted)   = mergeSortWithInversions left
        (rightInversions, rightSorted) = mergeSortWithInversions right
        (mergeInversions, sorted)      = mergeWithInversions leftSorted rightSorted

inversions :: Ord a => [a] -> Int
inversions = fst . mergeSortWithInversions

mergeSort :: Ord a => [a] -> [a]
mergeSort = snd . mergeSortWithInversions

prop_sorted :: [Int] -> Bool
prop_sorted as = sort as == mergeSort as

naiveInversions :: Ord a => [a] -> Int
naiveInversions [] = 0
naiveInversions (a:as) = length (filter (<a) as) + naiveInversions as

prop_inversions :: [Int] -> Bool
prop_inversions as = naiveInversions as == inversions as

main = do
  print $ mergeSortWithInversions [2,3,8,6,1]
  quickCheck prop_sorted
  quickCheck prop_inversions