I´m learning about the MergeSort algorithm. I´m using Python and have fed the algorithm with this unordered array: [38, 27, 3, 10, 9, 82, 43].
The code looks like this:
def mergeSort(lst):
if len(lst) > 1:
mid = len(lst)//2 # floor division to find the middle of the list.
L = lst[:mid] # creates two sublists, L and R, from the two halves.
R = lst[mid:]
mergeSort(L) # recursively performs mergeSort on each sublist.
mergeSort(R)
i = j = k = 0
print("L is ", L, " and R is ", R) # TTTTTT
while i < len(L) and j < len(R):
if L[i] < R[j]: # starts comparing the elements of each sublists to
assemble a sorted list
lst[k] = L[i] # if the N:th element in sublist L is smaller than
the N:th element in sublist R...
i += 1 # then the N:th element in lst must be taken from L
else: # And vice versa
lst[k] = R[j]
j += 1
k += 1 # increment the variables with one to continue to
the next index position.
while i < len(L):
lst[k] = L[i] # loops back over the sublists
i += 1
k += 1
while j < len(R):
lst[k] = R[j]
j += 1
k += 1
print("This is list", lst) # BBBBBB
I don´t understand the control flow of the algorithm. I inserted two print statements to help myself track the flow (what I have noted as #TTTTT and #BBBBB, respectively). I noticed from these prints that the algorithm breaks down the original array into sublists such that we get, for example, [38], [27] and [3]. It then compares L = [27] to R = [3]. Since 27 > 3 it sorts these two sublists and merges them into lst = [3, 27]. We have now reached the end of this particular loop. Next, control moves up again and prints "This is L [38] and this is R [3, 27]".
My question is how R suddenly equates to the sorted sublist, lst = [3, 27]. How does control identify lst with R and L when it starts to merge the sublists back into one?
