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?
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
while i < len(lefthalf):
while j < len(righthalf):
while loop pick a smaller smaller item from
righthalf until one of two lists run out. (
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
alist[k] = ... change the item of
alist in place.