{-# LANGUAGE UnicodeSyntax #-}
module Inversions (inversions) where

inversions ∷ Ord α ⇒ [α] → Int
inversions = fst . inversions'
  where
    inversions' list@(_:_:_) = (leftInvs + rightInvs + splitInvs, sortedList)
      where (leftInvs, leftSortedList) = inversions' leftList
            (rightInvs, rightSortedList) = inversions' rightList
            (splitInvs, sortedList) = mergeInvs leftSortedList rightSortedList
            (leftList,rightList) = splitAt ((`div` 2) $ length list) list
    inversions' list = (0, list)

mergeInvs ∷ Ord α ⇒ [α] → [α] → (Int,[α])
mergeInvs = mergeInvs' 0
  where mergeInvs' i a [] = (i, a)
        mergeInvs' i [] a = (i, a)
        mergeInvs' i (x:xs) ylist@(y:_) | x < y = (i + invs, x : invList)
          where (invs, invList) = mergeInvs' 0 xs ylist
        mergeInvs' i xlist (y:ys) = (i + invs + length xlist, y : invList)
          where (invs, invList) = mergeInvs' 0 xlist ys