Counting Inversions

Objectives

The objective of PA3 is to create a program that counts inversions. Your countInv code must be based on merge sort and must run in O(n log n) time, where n is the input size. See the Counting Inversions lecture for a discussion of the algorithm.

Download the file countInv.txt, and rename it countinv.py. Implement the functions marked # implement (do not rename them or change their arguments) and check in your code as countinv.py. The Checkin tab on the course website will perform preliminary testing of your code. These tests do not indicate your final grade. They can, however, catch mistakes in your submission. You can re-submit your file as often as you want.

Testing your code

Given the input file test.txt, your program:

  python3 countinv.py test.txt

  15