0

I am trying to implement the famous : Counting inversions using merge sort. I wrote the code for the same. The code works well for small data. I had a few test cases using which I verified the answer. But the code takes an awful long time when the input is large (100000). So, I just want to make sure that the complexity of my code is O(N lgN) and not higher (being of higher complexity, it might be taking longer time). Here is my code in Python:

    def merge_sort(u_list,inv):
    if(len(u_list) == 1): return 0
    if(len(u_list)>1):
        mid=len(u_list)//2
        l_list=u_list[:mid]
        r_list=u_list[mid:]
        a=merge_sort(l_list,inv)
        b=merge_sort(r_list,inv)
        count=0

        i=0
        j=0
        k=0
        track=0
        while i<len(l_list) and j<len(r_list) :
            if l_list[i]<=r_list[j]:
                u_list[k]=l_list[i]
                track+=1
                i+=1
                k+=1

            else: #r_list[j]<l_list[i]
                u_list[k]=r_list[j]
                inv=inv+(len(l_list)-track)
                j+=1
                k+=1

        while i<len(l_list) :
            u_list[k]=l_list[i]
            i+=1
            k+=1

        while j<len(r_list):
            u_list[k]=r_list[j]
            j+=1
            k+=1
        count=inv+a+b
        return count

inv=0
m=0
u_list=[]
x=0
for m in range(0,100000):
    x=int(input())
    u_list.append(x)

foo = merge_sort(u_list,inv)
print(foo)
  • can you profile your code? i.e. are you sure it does not spend most time on input? – Ashalynd Oct 18 '15 at 23:45
  • I can't see anything wrong so I agree that the problem might be in reading and parsing input. Put a `print` before `foo = merge_sort(u_list,inv)` to make sure that it's finished that stage and is sorting. – Alex Hall Oct 19 '15 at 02:07
  • related: `O(n log n)` implementation [`sort_and_count()`](http://stackoverflow.com/a/2989341/4279) – jfs Oct 19 '15 at 04:54

2 Answers2

0

I replaced 

for m in range(0,100000):
    x=int(input())
    u_list.append(x)

with

from random import *
u_list = list(range(100000))
shuffle(u_list)

and ran the code and it took about a second, which seems normal. I think your merge sort is fine and something is going wrong on input. How are you passing input to the script? If you are streaming in some big text file is it possible the file isn't 100000 lines and the program just waits forever?

Alex Hall
  • 34,833
  • 5
  • 57
  • 89
  • Actually I am using www.ideone.com . I think that is not the best method. –  Oct 19 '15 at 10:59
  • Yes, I realized something was wrong with the input. I have posted the corrected version. Thanks for your help. –  Oct 19 '15 at 18:41
0

Since I was having the input data in a text file, I replaced :

x=0
for m in range(0,100000):
    x=int(input())
    u_list.append(x)

with this:

fileName = 'IntegerArray.txt'
u_list = []
with open(fileName) as f:
    for line in f:
        u_list.append(int(line))

And got the output in a second or so.