Python MergeSort

Question

我正在尝试实现Python合并排序，但在某些方面失败了。我得到的伪代码是准确的，但看起来像是为不同的语言构建的。

伪代码需要满足以下条件

输入数组大小的/declare数组temp a

我不确定这在Python中是如何实现的。无论如何，代码如下。整个想法是，我需要对数组/列表进行排序，并返回排序后的数组/列表。

到目前为止，它失败了，并显示以下消息。我会说这是因为新的临时数组/列表，但我不确定

Traceback (most recent call last):  
  File "./mergesort", line 56, in <module>  
    main()  
  File "./mergesort", line 52, in main  
    mergesortbase(array)  
  File "./mergesort", line 4, in mergesortbase  
    mergesort(num, 0, len(num)-1)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 12, in mergesort  
    merge(num, low, mid, mid+1, high)  
  File "./mergesort", line 27, in merge  
    temp[k] = a[j]  
IndexError: list assignment index out of range  

注意:完全修改代码没有帮助，因为我将需要使用确切的伪代码。

#!/usr/bin/python3.6

def mergesortbase(num):
    mergesort(num, 0, len(num)-1)


def mergesort(num, low, high):
    if low < high:
      mid = (low + high) // 2
      mergesort(num, low, mid)
      mergesort(num, mid+1, high)
      merge(num, low, mid, mid+1, high)

def merge(a, l1, u1, l2, u2):
# declare array temp of size of input array a
# Comment -- Not doable in Python to create array/list with specific size
    temp = []
    i = l1
    j = l2
    k = l1

    while (i <= u1 and j <= u2):
      if (a[i] <= a[j]):
         temp[k] = a[i]
         i = i + 1
      else:
         temp[k] = a[j]
         j = j + 1

      k = k + 1

    while ( i <= u2 ):
       temp[k] = a[i]
       k = k + 1
       i = i + 1

    while ( j <= u2 ):
       temp[k] = a[j]
       k = k + 1
       i = i + 1

    h = l1

    while ( h <= u2 ):
       a[h] = temp[h]
       h = h + 1


def main():
   array = [8, 5, 7, 1, 9, 3]
   mergesortbase(array)


if __name__ == "__main__":
  main()

Answer 1

你能不能只复制一个输入数组？

temp = a.copy()

它的尺寸是一样的。

如果您想将temp中的所有元素初始化为某个值，请使用如下内容：

temp =* len(a)

Answer 2

看一下这篇文章，应该能够得到理解mergesort所需的答案

MergeSort