user99137 - 1 year ago 61
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
``````

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.