NumberOfInversions

using System;
using System.IO;
using System.Linq;

namespace NumberOfInversions
{
    /// <summary>
    /// Algorithms: Design and Analysis by Tim Roughgarden
    /// Part 1, Programming Question - 1
    /// </summary>
    /// <see>
    /// https://class.coursera.org/algo-007/quiz?quiz_type=homework
    /// </see>
    public sealed class Program
    {
        static void Main(string[] args)
        {
            var a = File.ReadLines(args[0]).Select(int.Parse).ToArray();
            Console.WriteLine(new Program().Run(a));
        }

        public Int64 Run(int[] a)
        {
            return Run(a, 0, a.Length);
        }

        private Int64 Run(int[] a, int l, int r)
        {
            if (r - l < 2)
            {
                return 0;
            }

            var m = l + (r - l) / 2;
            var leftInversionCount = Run(a, l, m);
            var rightInversionCount = Run(a, m, r);

            var i = l;
            var j = m;
            var k = 0;
            var temp = new int[r - l];
            var splitInversionCount = 0;

            for (; k < temp.Length && i < m && j < r; k++)
            {
                if (a[i] < a[j])
                {
                    temp[k] = a[i];
                    i++;
                }
                else
                {
                    temp[k] = a[j];
                    j++;
                    splitInversionCount += (m - i);
                }
            }

            for (; i < m; i++, k++)
            {
                temp[k] = a[i];
            }

            for (; j < r; j++, k++)
            {
                temp[k] = a[j];
            }

            temp.CopyTo(a, l);
            return checked(leftInversionCount + rightInversionCount + splitInversionCount);
        }
    }
}