Skip to content

Instantly share code, notes, and snippets.

@andreis
Created March 3, 2014 16:55
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save andreis/9329283 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
# https://www.hackerrank.com/challenges/insertion-sort
count = 0
def mergesort(L, l, r):
if l+1 >= r: return
mid = int((l+r+1)//2)
mergesort(L, l, mid)
mergesort(L, mid, r)
merge(L,l,mid,r)
def merge(L, l, mid, r):
if l+1 >= r: return
global count
left , right = L[l:mid], L[mid:r]
ri, li = 0, 0
for i in range(l, r):
if li == len(left):
L[i] = right[ri]
ri += 1
elif ri == len(right):
L[i] = left[li]
li += 1
elif left[li] <= right[ri]:
L[i] = left[li]
li += 1
else:
L[i] = right[ri]
count += ri + mid - i
ri += 1
tests = int(input())
out = ''
for _idx in range(tests):
n = int(input())
total = 0
L = [int(i) for i in input().split()]
count = 0
mergesort(L, 0, len(L))
out += str(count)
out += '\n'
print(out[:-1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment