Skip to content

Instantly share code, notes, and snippets.

@nfrancois
Created July 2, 2013 21:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nfrancois/5913531 to your computer and use it in GitHub Desktop.
Save nfrancois/5913531 to your computer and use it in GitHub Desktop.
def arrayFromFile(filename):
with open(filename) as f:
return list(int(line) for line in f)
def countSplitInv(left, right):
nb_inv = i = j = 0;
n = len(left) + len(right)
array = [0] * n
for k in range(0, n):
if i >= len(left):
array[k] = right[j]
j+=1
elif j >= len(right):
array[k] = left[i]
i+=1
elif left[i] <= right[j]:
array[k] = left[i]
i+=1
else:
array[k] = right[j]
j+=1;
nb_inv+=len(left) - i
return array, nb_inv
def count(array):
n = len(array)
if n == 1:
return array, 0
else:
m = int(n/2)
left, x = count(array[0:m])
right, y = count(array[m:n])
sortedArray, z = countSplitInv(left, right)
nb_inv = x + y + z
return sortedArray, nb_inv
myFile = "IntegerArray.txt"
input_array = arrayFromFile(myFile)
output_array, result = count(input_array)
print(result);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment