如何追查此合并功能中的错误？

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]

编辑

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

Answer 1

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

另请注意，将 right 作为 1 + 切片最后一个元素的索引传递会更具可读性和一致性，这与 python 中的切片表示法一致并且会删除这里和那里的 +1/-1 调整。 right 包含的约定在 java 类中进行了教导，但它容易出错并且不允许空切片。

使用更简单的索引变量名称将有助于提高可读性，尤其是缩进更多 space。

这是修改后的版本：

# sort the elements in toSort[left:right]
def merge_sort(toSort, left, right):
   # check if we have more than one remaining element
   if right - left < 2:
      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, right)
   # merge the results
   merge(toSort, left, mid, right)

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

   # variables to track position in left and right lists and the sorted list
   i = 0
   j = 0
   k = left

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

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

   while j < len(rightList):
      toSort[k] = rightList[j]
      j += 1
      k += 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))
print(unsorted)

如何追查此合并功能中的错误？

How to track down the mistake in this merge function?

mergesort

python-3.x

编辑