what's wrong with this merge sort python code?

Question

Here is the code for merge sort.. The code works very well and sorts the numbers. But if we go larger data that has to be sorted, something goes wrong. The data to be sorted contains numbers which are not repeated. But after sorting , there are certain numbers which gets repeated many times. I dont understand why is that.. And this happens when i give a dataset of 100000 numbers. when smaller data is to be sorted, the code works very well.

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)/2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1


print("select the file: ")
file_name =  tkFileDialog.askopenfile(mode='r', title='Select word list file')
inv_data = np.loadtxt(file_name,dtype='float', comments='#', delimiter=None, converters=None, skiprows=0, usecols=None,
                unpack=False, ndmin=0)
mergeSort(inv_data)
print("sorted list :", inv_data)

The data set is here in the below link http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt

I could not reproduce your problem. Using this, I got 100000. mergeSort(t) print len(set(t)) I did not use your file reading method, so the problem could be there. — user189
– user189, Commented May 6, 2014 at 12:13
@user3317704, using your np.loadtxt and my own merge sort algorithm works fine, I get 1000000 numbers sorted with no repetition. — Padraic Cunningham
– Padraic Cunningham, Commented May 6, 2014 at 13:47

Janne Karila · Accepted Answer · 2014-05-06 12:32:54Z

5

I guess you tested with Python lists when you found the code working very well. Now you a using it with a NumPy array. The crucial difference is that slicing a NumPy array as in here

lefthalf = alist[:mid]
righthalf = alist[mid:]

creates views over the original array, while slicing a list creates copies.

When your algorithm overwrites alist by merging lefthalf and righthalf, all three lists must be separate; otherwise it may overwrite items lefthalf that have not yet been merged.

The bug can be triggered by a small array:

>>> l = np.arange(10,0,-1)
>>> l
array([10,  9,  8,  7,  6,  5,  4,  3,  2,  1])
>>> mergeSort(l)
>>> l
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

edited May 6, 2014 at 12:32

answered May 6, 2014 at 12:14

Janne Karila

25.3k6 gold badges59 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user 3317704 Over a year ago

Understood perfecrtly. Thanks a lot. converted my data file from numpy array to list using tolist(). My code works perfectly well. thanks a lot :)

Collectives™ on Stack Overflow

what's wrong with this merge sort python code?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related