这个归并排序的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。它涉及到IT技术方面的内容。

- user 3317704

---

我无法复现您的问题。使用这个代码，我得到了100000。`mergeSort(t)` `print len(set(t))`我没有使用您的文件读取方法，因此问题可能出在那里。 - user189

@user3317704，使用您的np.loadtxt和我的归并排序算法可以很好地工作，我成功地将1000000个不重复的数字排序。 - Padraic Cunningham

Answer 1

我猜你在测试时使用了Python列表，发现代码运行得非常好。现在你要使用NumPy数组。关键的区别在于像这样对NumPy数组进行切片

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

创建数组视图时，视图是原始数组的表示，而切片列表则会创建副本。

当您的算法通过合并lefthalf和righthalf来覆盖alist时，所有三个列表必须是独立的；否则它可能会覆盖尚未合并的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])

- Janne Karila

---

完全理解了，非常感谢。我使用tolist()将我的数据文件从numpy数组转换为列表。我的代码运行得非常完美。非常感谢 :) - user 3317704