Inversions

inversions.hs

module Main where
import System.IO
import System.Environment (getArgs)

main = do
  handle <- openFile "IntegerArray.txt" ReadMode
  numbers <- fmap (map read . lines) $ hGetContents handle
  print (countInversions numbers)
  hClose handle
  
countInversions :: (Num a, Ord a) => [a] -> Integer
countInversions = snd.merge_sort_count


merge_and_count  :: (Num a, Ord a) => [a] -> [a] -> Integer -> ([a], Integer)
merge_and_count l1@(x:xs) l2@(y:ys) cnt | x < y     = add_item x $! (merge_and_count xs l2 cnt)
                                        |otherwise  = add_item y $! (merge_and_count l1 ys (cnt + (fromIntegral (length l1))))
                            where 
                                add_item x (xs, a) = (x:xs, a)
merge_and_count l1 l2 cnt = (l1 ++ l2, cnt)                


merge_sort_count :: (Num a, Ord a) => [a] -> ([a], Integer)
merge_sort_count []  = ([], 0) 
merge_sort_count [x] = ([x], 0)
merge_sort_count xs  = merge_and_count l1 l2 (count1 + count2)
       where 
           (l1, count1) = merge_sort_count $! (take h xs)
           (l2, count2) = merge_sort_count $! (drop h xs)
           h = length xs `div` 2

inversions.rb

def merge_and_count(arr_left, arr_right)
  result = []
  inversion_count = 0
  while (!arr_left.empty? && !arr_right.empty?)
    if (arr_left.last <= arr_right.last)
      result << arr_left.pop
    else
      result << arr_right.pop
      inversion_count += arr_left.length
    end    
  end
  return [result + arr_left.reverse, inversion_count] unless (arr_left.empty?)
  [result + arr_right.reverse, inversion_count]
end 

def invert_and_sort(arr)
  return [arr, 0] if (arr.empty? || arr.length == 1)
  midway = arr.length / 2 - 1
  arr_left, invert_left = invert_and_sort(arr[0..midway])
  arr_right, invert_right = invert_and_sort(arr[(midway+1)..-1])
  return merge_and_count(arr_left.reverse, arr_right.reverse).tap{|a| a[1] += invert_left + invert_right}
end  
data = File.read('IntegerArray.txt').split("\n").map(&:to_i)
puts invert_and_sort(data).inspect