Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(NlogN) solution in Speedy category for Count Inversions by nickie
def count_inversion(sequence):
# we need the sequence to be mutable for this to work
if type(sequence) is not list:
sequence = list(sequence)
# divide and conquer: count inversions in sequence[first:last]
# important invariant: afterwards sequence[first:last] will be sorted
def count(first, last):
# recursion ends when there are too few elements
if last - first < 2:
return 0
# divide in two halves and count inversions separately
mid = (first+last)//2
inversions = count(first, mid)
inversions += count(mid, last)
# then add cross-half inversions while merging the two halves
i, j = first, mid
ordered = []
while i
Sept. 16, 2014
Comments:
