user99137 user99137 - 5 months ago 5
Python Question

Merge sort, where are the sublists saved?

I have included the code I am using.

I understand that the start of the code continues splitting the sublists until you have single values. The single values are saved in the variables lefthalf and righthalf and are then merged in sorted order.

How does the code merge two lists of two elements? As I see it these sublists are saved in separate local variables called alist, how are these being merged?

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

The first while loop pick a smaller smaller item from lefthalf, righthalf until one of two lists run out. (lefthalf, righthalf each contains sorted items)

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

The second, third while loops copies remaining items to alist. Only one of two loop bodies will be executed; one is exausted in the first while loop.


SIDE NOTE: alist[k] = ... change the item of alist in place.