Inversions.cs

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

namespace Algorithms
{
	// Download the text file here. (Right click and save link as)
	// This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

	// Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

	// Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. 
	// The numeric answer for the given input file should be typed in the space below.

	// So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / any other punctuation marks.
	// You can make up to 5 attempts, and we'll use the best one for grading.

	// (We do not require you to submit your code, so feel free to use any programming language you want --- just type the final numeric answer in the following space.)

	// [TIP: before submitting, first test the correctness of your program on some small test files or your own devising. 
	// Then post your best test cases to the discussion forums to help your fellow students!]
	public class Inversions
	{
		public string InputFileName {
			get;
			set;
		}

		public int[] Integers {
			get;
			set;
		}

		public Inversions (string inputFileName)
		{
			InputFileName = inputFileName;

			if (!File.Exists (InputFileName)) 
			{
				throw new FileNotFoundException ();
			}

			Integers = Array.ConvertAll (File.ReadAllLines (InputFileName), int.Parse);
		}

		// Main recursive algorithm.
		public int GetInversions(int[] integers)
		{
			if (integers.Length == 1) 
			{
				return 0;
			}
				
			int midPoint = integers.Length / 2;
			var leftInversions = GetInversions (integers.Take (midPoint).ToArray());
			var rightInversions = GetInversions (integers.Skip (midPoint).Take (integers.Length - midPoint).ToArray());
			var splitInversions = CountSplitInversions (integers);

			return leftInversions + rightInversions + splitInversions;
		}

		private int CountSplitInversions (int[] integers)
		{

			return 1;
		}
	}
}