python-3.x - 错误的合并排序实现

Question

我的合并排序实现有问题，因为在调用合并之前我没有得到两个排序列表。我不确定它有什么问题。

def mergeSort(arr):
    if len(arr) == 1 : return arr
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    mergeSort(left_half)
    mergeSort(right_half)
    return merge(left_half,right_half)

def merge(list1,list2):
  res = []
  i = 0
  j = 0
  while i < len(list1) and j < len(list2):
    if list1[i] < list2[j]:
      res.append(list1[i])
      i += 1
    elif list1[i] > list2[j]:
      res.append(list2[j])
      j += 1
  #Add remaining to res if any
  while i < len(list1):
    res.append(list1[i])
    i += 1
  while j < len(list2):
    res.append(list2[j])
    j += 1
  return res

A = [5,1,2,15]
print(mergeSort(A))

我对合并排序的理解是空间复杂度是 O(n)，因为内存中有 n 个项目(在最终合并中)。快速排序是否优于合并排序只是因为快速排序就地？

Answer 1

我不是python专家，但你应该写

left_half = arr[:mid]
right_half = arr[mid:]

left_half = mergeSort(left_half)
right_half = mergeSort(right_half)

因为您的 mergeSort 返回已排序数组的副本。