Codecademy归并排序算法

Question

我目前正在学习使用 Python 进行排序算法的代码学院课程，并且我目前正在学习合并排序。但是，显示的代码似乎与他们显示的图表相矛盾。

def merge_sort(items):
  if len(items) <= 1:
    return items

  middle_index = len(items) // 2
  left_split = items[:middle_index]
  right_split = items[middle_index:]

  left_sorted = merge_sort(left_split)
  right_sorted = merge_sort(right_split)

  return merge(left_sorted, right_sorted)

def merge(left, right):
  result = []

  while (left and right):
    if left[0] < right[0]:
      result.append(left[0])
      left.pop(0)
    else:
      result.append(right[0])
      right.pop(0)

  if left:
    result += left
  if right:
    result += right

  return result

同时，这是反映此遍历的图表：

所以，图表向我展示了列表首先拆分的方式是左侧拆分应该是从开始到包括中间索引的所有数字.然而，代码说左拆分应该是从开始到 而不是 的所有数字，包括中间索引。我只是疯了还是这没有意义？就第一次拆分而言，此代码是否与图表相矛盾？

Answer 1

对于图中的例子，

items = [98, 13, 274, 7, 12, 981, 5]

len(items) 将是 7，而 middle_index 将是 7 // 2 = 3，因此

left_split = items[:3] = [98, 13, 274]
right_split = items[3:] = [7, 12, 981, 5]

所以你是对的，代码将在右分割中包含中间元素，而在图像中它包含在左分割中。

然而，这并不意味着代码没有意义，因为 merge 函数相对于 left 和 right 是对称的，它不假设其中一个列表大于另一个列表；一旦合并过程中任一列表变空，剩余的另一个列表将附加到结果的末尾。

事实上，准确的分割点与排序结果无关，如果它尽可能靠近中间，算法会更有效，因为这会最小化每个分割的两个长度中的较大者。

Codecademy归并排序算法

Codecademy Merge sort Algorithm

python

sorting

mergesort