这个合并排序python代码有什么问题？

Question

这是合并排序的代码..代码工作得很好,并对数字进行排序.但是,如果我们要更大的数据必须进行排序,那么就会出现问题.要排序的数据包含不重复的数字.但是在排序之后,有一些数字会重复多次.我不明白为什么会这样......当我给出100000个数字的数据集时会发生这种情况.当要对较小的数据进行排序时,代码非常有效.

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)

数据集位于以下链接 http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt

Answer 1

当您发现代码运行良好时,我猜您使用Python列表进行了测试.现在你使用NumPy数组.关键的区别在于切割NumPy数组,就像在这里一样

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

创建原始数组的视图,而切片列表创建副本.

当你的算法将覆盖alist通过合并lefthalf和righthalf所有三个列表必须是独立的; 否则它可能会覆盖lefthalf尚未合并的项目.

该错误可以由一个小数组触发:

>>> 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])