Merge sort count inversions

Question

def mergeCount(left,right,invCount):
 inversionCount = invCount
 # print(left,right)
 for right_item in right:
 offset = 0
 insertState = False
 for i in range(len(left)):
 if left[i] <= right_item:
 offset += 1
 elif left[i] > right_item:
 inversionCount += len(left) - offset
 left.insert(i,right_item)
 # print("inserted",right_item)
 insertState = True
 break
 if not insertState:
 left.append(right_item)
 # print("new array is",left)
 return left,inversionCount
def mergeSortInversion(array):
 if len(array) <= 1:
 return array,0
 else:
 left_arr, left_count = mergeSortInversion(array[:len(array)//2])
 right_arr, right_count = mergeSortInversion(array[len(array)//2:])
 # print(left_arr,right_arr,left_count+right_count) 
 return mergeCount(left_arr,right_arr,left_count + right_count)

My merge sort code is taking the same amount of time as the brute force method for some reason. How can I fix the implementation or make it better?

• Dan Oberlam: Have you tried profiling it? Can you show the test cases and timing setup you're using?
• Gareth Rees: When you take a slice of a list in Python, like array[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leave array unsliced and instead pass the indexes of the start and end of the slice as parameters.
• Alex.S: There's no need in inversionCount, you can manipulate invCount directly

Answer 1

Comments

To reduce clutter, remove the commented-out code, such as:

# print(left,right)

Layout

The PEP 8 style guide recommends 4-space indent levels

Also, there should be whitespace around operators.

The black program can be used to automatically reformat the code for consistency.

Simpler

This line:

elif left[i] > right_item:

can be simplified as:

else:

This could help speed things up since the elif clause does not need to be evaluated.

Naming

The PEP-8 guide also recommends snake_case for function and variable names. For example:

mergeCount as merge_count

invCount as inv_count

It is common practice for array variables to be plural nouns. Also, the name array is not very descriptive. numbers would be better.

left_arr could be lefts, and right_arr could be rights.

Documentation

PEP-8 recommends adding docstrings for functions.

It would be good for mergeSortInversion to mention that it is called recursively.