Count inversion in python (for large integer array)

Question

I making a program for count inversion in pyhton and using python27 for the same. I have implement the alogorithm using divide and conquer technique(merge sort trick). My program runs fine for an input array of size uptill 100 (that's the max I could verify). Now i tested my program on an input array of size 50,000 and 1,00,000 but how ever i could not get correct answers. I have pasted my code below, kindly point out any possible mistake:

    f=open('forum.txt')
    a=[]
    s=1
    for line in f:
        a.append(line)





def CountInversion(IntegerArray):
_count=0
lc=0
rc=0
RightArray=[]
LeftArray=[]
if len(IntegerArray)>1:
        LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2])
        RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:])
elif len(IntegerArray)==1:
    return IntegerArray,0
ResultArray=IntegerArray
i=0
l=len(ResultArray)
j,k=0,0
for i in range(0,l):
    if j<len(RightArray) and k<len(LeftArray):
        if RightArray[j]<LeftArray[k]:
            ResultArray[i]=RightArray[j]
            j += 1
            a=(len(LeftArray)-k)
            _count = _count + a    
        else:
            ResultArray[i]=LeftArray[k]
            k += 1
elif j<len(RightArray):
    ResultArray[i]=RightArray[j]
        j += 1
elif k<len(LeftArray):
        ResultArray[i]=LeftArray[k]
        k += 1          
return ResultArray,(_count+lc+rc)

arr,b=CountInversion(a)

print ('end of inversions')

print b

I also ran the code given by J.F. Sebastian in this post, but the results are same(answers are correct for small input but not for input array of size 50000 or 1,00,000)

Answer 1

Your first problem is that you have inconsistent indentation. On a few lines you're using tabs instead of spaces, which is a very bad idea. Indentation is significant in Python, so it is easy to make errors if you don't watch out.

The second problem that I think you're having is that you're comparing strings, rather than numbers. Python is perfectly happy to sort strings, but it will use lexicographical orering, which can be unexpected when applied to integers encoded as strings. For example, the string "11" will be sorted ahead of the string "2", since it's first character 1 comes before 2 in the ASCII character set (and also in Unicode).

As I asked in a comment, it's not clear how you're determining that your code isn't working correctly. It may be that simply fixing the issues I described above will fix the problems you're having. If they do not, please explain how you're determining that your results are invalid and I'll try to update this post with further suggestions.

Answer 2

The problem is solved by parsing string to int and populating the array