归并排序，子列表保存在哪里

Question

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

我理解代码的开头会继续分割子列表，直到得到单个值。单个值保存在变量lefhalf和righthalf中，然后按排序顺序合并。

代码如何合并两个元素的两个列表?我看到这些子列表保存在单独的局部变量list中，它们是如何合并的?

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的条目。

Answer 2

所以这是mergeSort的原位版本，因为它接受列表并将其修改为排序版本。(虽然它需要为每一半创建一个副本，所以它不是恒定的空间)。这里是关于代码正在做什么的注释:

def mergeSort(alist):
    if len(alist)>1:  # empty lists and lists of one element are sorted already
        mid = len(alist)//2  # find the halfway point
        lefthalf = alist[:mid]  # make a copy of the first half of the list
        righthalf = alist[mid:] # make a copy of the second half of the list 
        mergeSort(lefthalf)
        mergeSort(righthalf)
        # Each half is now sorted
        # Now we're going to copy elements from lefthalf and righthalf
        # back into alist. We do this by keeping three index variables:
        # where we are in lefthalf (i), where we are in righthalf (j)
        # and where we are going to put stuff in alist (k)
        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            # that is, "while we still have stuff left in both halves":
            if lefthalf[i] < righthalf[j]:
                # The thing we're looking at in lefthalf is smaller
                # than what we have in righthalf. Copy the thing in
                # lefthalf over to alist, and increment i
                alist[k]=lefthalf[i]
                i=i+1
            else:
                # same story, but on the right half
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        # If we ran out of stuff in righthalf first, finish up copying
        # over all the rest of the stuff in lefthalf
        while i < len(lefthalf): 
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        # If we ran out of stuff in lefthalf first, finish up copying
        # over all the rest of the stuff in righthalf
        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
        # Note that only one of those while loops will actually do anything -
        # the other while loop will have its condition false the first time