inversion.ex

defmodule Inversion do

  def summarize(a, b, acc, list_acc) do
    case {a, b} do
      {[], []} -> {list_acc, acc}
      {a, []} -> {Enum.reverse(a) ++ list_acc, acc}
      {[], b} -> {Enum.revserse(b) ++ list_acc, acc}
      {a,b} when hd(a) > hd(b) -> summarize(a, tl(b), length(a) + acc, [hd(b) | list_acc])
      {a,b} when hd(a) <= hd(b) -> summarize(tl(a), b, acc, [hd(a) | list_acc])
    end
  end

  def count_inversion(a, n) do
    case a do
      [] -> {[], 0}
      [x] -> {[x], 0}
      [x,y] when x > y -> {[y,x], 1}
      [x,y] when x <= y -> {[x,y], 0}
      a -> 
        half = div(n, 2)
        {sorted_b, x} = count_inversion(Enum.slice(a, (0 .. half-1)), half)
        {sorted_c, y} = count_inversion(Enum.slice(a, half..n-1), n - half)
        {sorted_a, z} = summarize(sorted_b, sorted_c, 0, [])
        {Enum.reverse(sorted_a), x + y + z}
    end
  end

  def read(filename) do
    fstream = File.stream!(filename)
    l = Enum.map(fstream, fn(x) -> String.to_integer(String.trim(x)) end)
    {sorted, ans} = count_inversion(l, length(l))
    ans
  end
end