2-Counting-Inversions

README

Counting Inversions

Complexity Analysis:

• Time complexity: O(n log₂ n).
• Space complexity: O(n).

Programming Assignment #2

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 i^th row of the file indicates the i^th 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.