## Question

Project Description: the file “IntegerArray.txt” included in this project folder contains all 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 a divide-and-conquer algorithm.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import sysimport time

# increase the maximum recursion depth

sys.setrecursionlimit(10000)

def conquer(array: [], tmp: [], left: int, mid: int, right: int) -> int:

"""

conquer step, collect all result

:param array: array of integer

:param tmp: temporary array

:param left: left index

:param mid: mid index

:param right: right index

:return: number of insertion

"""

count = 0

ll = left

mm = mid

tt = left

# until reaching one of 2 ending

while ll < mid and mm <= right:

# a[i < a[j], no rul is broken

if array[ll] <= array[mm]:

tmp[tt] = array[ll]

tt += 1

ll += 1

pass

else:

# a[i] > a[j] , j > i

tmp[tt] = array[mm]

tt += 1

mm += 1

# sum up the

count += mid - ll

pass

pass

# copy the rest to tmp array

while ll < mid:

tmp[tt] = arr[ll]

tt += 1

ll += 1

pass

# copy the rest to tmp array

while mm <= right:

tmp[tt] = arr[mm]

tt += 1

mm += 1

pass

# copy tmp arry to the array

ll = left

while ll <= right:

array[ll] = tmp[ll]

ll += 1

pass

return count

pass

def divide(array: [], tmp: [], left: int, right: int) -> int:

"""

divide array and collect insertion number

:param array: the array

:param tmp: the temporary array

:param left: left index

:param right: right index

:return:

"""

count = 0

if left < right:

# get mid index

mid = int((left + right) / 2)...

By purchasing this solution you'll be able to access the following files:

Solution1.zip and Solution2.docx.