# Inversion count using merge sort

count = 0

def merge_sort(li):

if len(li) < 2: return li
m = len(li) / 2
return merge(merge_sort(li[:m]), merge_sort(li[m:]))

def merge(l, r):
global count
result = []
i = j = 0
while i < len(l) and j < len(r):
if l[i] < r[j]:
result.append(l[i])
i += 1
else:
result.append(r[j])
count = count + (len(l) - i)
j += 1
result.extend(l[i:])
result.extend(r[j:])
return result

unsorted = [10,2,3,22,33,7,4,1,2]
print merge_sort(unsorted)
print count

• Do you mean it to be a simple code review? Or is there any specific aspect of the code that you would like reviewed? Jun 22, 2012 at 7:12
• I just want the code to be minimalistic and also readable... so if there is any improvement in that aspect then I would definitely like some positive criticism. Jun 22, 2012 at 7:16
• The code doesn't work as expected: change unsorted -> u_list Jun 22, 2012 at 9:56
• Some of the following suggestions make the error of using pop(0). Unlike pop(), which pops the last element and takes O(1), s.pop(0) gives O(n) runtime (rearranging the positions of all other elements). This breaks the algorithmic O(nlogn) concept and turns the runtime to O(n^2). Oct 18, 2015 at 8:14
• Added my own version for codereview here: codereview.stackexchange.com/questions/107928/… Oct 19, 2015 at 5:56

Rather than a global count, I would suggest using either a parameter, or to return a tuple that keeps the count during each recursive call. This would also assure you thread safety.

def merge_sort(li, c):
if len(li) < 2: return li
m = len(li) / 2
return merge(merge_sort(li[:m],c), merge_sort(li[m:],c),c)

def merge(l, r, c):
result = []


Since l and r are copied in merge_sort, we can modify them without heart burn. We first reverse the two lists O(n) so that we can use s.pop() from the correct end in O(1) (Thanks to @ofer.sheffer for pointing out the mistake).

    l.reverse()
r.reverse()
while l and r:
s = l if l[-1] < r[-1] else r
result.append(s.pop())


Counting is separate from the actual business of merge sort. So it is nicer to move it to a separate line.

        if (s == r): c += len(l)


Now, add what ever is left in the array

    rest = l if l else r
rest.reverse()
result.extend(rest)
return result

unsorted = [10,2,3,22,33,7,4,1,2]


Use a mutable DS to simulate pass by reference.

count = 
print merge_sort(unsorted, count)
print count

• Unlike pop(), which pops the last element and takes O(1), s.pop(0) gives O(n) runtime (rearranging the positions of all other elements). This breaks the algorithmic O(nlogn) concept and turns the runtime to O(n^2). Oct 18, 2015 at 8:12
• Thank you, I did not realize that. Since it is a major problem, would you like to make an answer of your own (I will note your comment in my answer, and point to yours if you do that)? Oct 18, 2015 at 23:02
• I added my own version for code review here: codereview.stackexchange.com/questions/107928/… - I used a loop over k values (subarray). For each of them I run "A[write_index]=value" which is O(1). Oct 19, 2015 at 6:00