python - 合并排序，子列表保存在哪里？

Question

我已经包含了我正在使用的代码。

我知道代码的开头会继续拆分子列表，直到您拥有单个值为止。单个值保存在变量 lefthalf 和 righthalf 中，然后按排序顺序合并。

代码如何合并两个包含两个元素的列表？正如我所见，这些子列表保存在称为 alist 的单独局部变量中，这些如何合并？

def mergeSort(alist):

    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0

        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1


        while i < len(lefthalf): 
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1


        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

Answer 1

第一个 while 循环从 lefthalf、righthalf 中选择一个较小的较小项目，直到两个列表中的一个用完。 (lefthalf、righthalf 每个都包含已排序的项目)

while i < len(lefthalf) and j < len(righthalf):
    if lefthalf[i] < righthalf[j]:
        # Pick the smallest item from `leftHalf` if has a smaller item
        alist[k]=lefthalf[i]
        i=i+1
    else:
        # Pick smallest item from `rightHalf`
        alist[k]=righthalf[j]
        j=j+1
    k = k + 1
    # `k` keeps track position of `alist`
    # (where to put the smallest item)
    # Need to increase the `k` for the next item

第二个、第三个while 循环将剩余的项目复制到alist。只会执行两个循环体中的一个；一个人在第一个 while 循环中筋疲力尽。

---

旁注:alist[k] = ... 更改 alist 的项目。