如何在此合并功能中查找错误？

Question

我不知道此合并排序实现的问题是什么。我已经确认问题是在merge函数而不是merge_sort中发生的，方法是使用在线发现的一些示例中的merge替换相同的函数，它可以正常工作，但是我在实现中找不到错误。

• 预期结果：列表按从小到大的顺序排序。

• 实际结果：列表的左侧已修改（未按顺序），右侧未修改。

我已经尝试在程序的各个位置添加打印语句，并且看起来该问题与rightList的创建不正确有关，但我不知道为什么。

我该怎么做才能找出原因？

代码：

def merge_sort(toSort, left, right):
  # check if we have more than one remaining element
  if left >= right:
    return
  # get middle of array, note the result needs to be an int
  mid = (left + right) // 2
  # call merge sort on the left and right sides of the list
  merge_sort(toSort, left, mid)
  merge_sort(toSort, mid+1, right)
  # merge the results
  merge(toSort, left, right, mid)

# merge function taking a list along with the positions 
# of the start, middle and end
def merge(toSort, left, right, mid):
  # split the list into two separate lists based on the mid position
  leftList = toSort[left:mid+1]
  rightList = toSort[mid+1:right+1]

  # variables to track position in left and right lists and the sorted list
  lIndex = 0 
  rIndex = 0
  sIndex = lIndex

  # while there are remaining elements in both lists
  while lIndex < len(leftList) and rIndex < len(rightList):

    #if the left value is less than or equal to the right value add it to position sIndex in toSort
    # and move lIndex to next position
    if leftList[lIndex] <= rightList[rIndex]:
      toSort[sIndex] = leftList[lIndex]
      lIndex = lIndex + 1
    # otherwise set sIndex to right value and move rIndex to next position
    else:
      toSort[sIndex] = rightList[rIndex]
      rIndex = rIndex + 1
    sIndex = sIndex + 1
  # add the remaining elements from either leftList or rightList
  while lIndex < len(leftList):
    toSort[sIndex] = leftList[lIndex]
    lIndex = lIndex + 1
    sIndex = sIndex + 1

  while rIndex < len(rightList):
    toSort[sIndex] = rightList[rIndex]
    rIndex = rIndex + 1
    sIndex = sIndex + 1

unsorted = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26]   
print(unsorted)
merge_sort(unsorted, 0, len(unsorted) - 1)
print(unsorted)

输出：

[33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26]

[16, 22, 26, 49, 31, 4, 48, 29, 49, 31, 4, 48, 16, 22, 26]

编辑

链接到colab中的代码示例：https://colab.research.google.com/drive/1z5ouu_aD1QM0unthkW_ZGkDlrnPNElxm?usp=sharing

Answer 1

toSort中的索引变量，sIndex应该初始化为left，而不是0。

还请注意，将right传递为1 +切片的最后一个元素的索引会更易读，更一致，这与python中的切片表示法一致，并且会删除+1 / -1在这里和那里进行调整。 Java类中讲授了包含right的约定，但是该约定容易出错，并且不允许有空片。

这里是修改后的版本：