# 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? – rahul Jun 22 '12 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. – user1468092 Jun 22 '12 at 7:16
• The code doesn't work as expected: change unsorted -> u_list – cat_baxter Jun 22 '12 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). – ofer.sheffer Oct 18 '15 at 8:14
• Added my own version for codereview here: codereview.stackexchange.com/questions/107928/… – ofer.sheffer Oct 19 '15 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[0] += 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 = [0]
print merge_sort(unsorted, count)
print count[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). – ofer.sheffer Oct 18 '15 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)? – rahul Oct 18 '15 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). – ofer.sheffer Oct 19 '15 at 6:00