1
\$\begingroup\$
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 / make it better?

\$\endgroup\$
  • \$\begingroup\$ Have you tried profiling it? Can you show the test cases and timing setup you're using? \$\endgroup\$ – Dannnno Jan 24 '18 at 17:15
  • \$\begingroup\$ 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. \$\endgroup\$ – Gareth Rees Jan 24 '18 at 17:18
  • \$\begingroup\$ There's no need in inversionCount, you can manipulate invCount directly \$\endgroup\$ – Alex.S Jan 26 '18 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.