Copy and split a List in Python3, Merge Sort

Question

I was trying to write the merge sort in python on my own, but returned a list nothing to do with several repeated numbers. When checking the solution code online, I was left with doubts about how to create and pass values from one list to the other, follows how it is written in código correto:

# a variável m desse código representa meio da lista
# create two empty arrays L[0..nL] and R[0..nR]
L = [0] * (nL + 1)
R = [0] * (nR + 1)

# copy left half of arr in L[0..nL-1]
for i in range(0, nL):
L[i] = arr[l + i]

# copy right half of arr in R[0..nR-1]
for j in range(0, nR):
R[j] = arr[m + 1 + j]

Next as eu escrevi:

# criei duas listas vazias
    R = []
    L = []
# passei metade da lista original para L
    for i in range(0, nL):
        tmp = a[i]
        L.append(tmp)
# a outra metade para R
    for j in range(nR, end):
        tmp = a[j]
        R.append(tmp)

whereas nL and nR split the list in half, the way in which I wrote results in a list other than the correct code?

p s..:link to the correct code

Answer 1

I took a look at the link of the code you passed, your way of writing is also correct but it is necessary to take into account some specific points, for example:

# a variável m desse código representa meio da lista
# create two empty arrays L[0..nL] and R[0..nR]
L = [0] * (nL + 1)
R = [0] * (nR + 1)

In this part, you can see that an L and R list has been created with a different index than you did, but this has an explanation.

During the code, it is perceived that the "Math.inf" was used as a sentinel value, ie:

# put infinity as sentinel value at the end of Both L and R
    L[nL] = math.inf
    R[nR] = math.inf

To facilitate at the time of analysis and ordering, he determined an "infinite" value at the end of each of these lists, thus:

# iterate over L and R
    # and copy the smallest of L[i] and R[j] to arr[k]
    i = 0
    j = 0
    for k in range(l, r + 1):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1

When the iteration is made, it will not run the risk of suffering an "index out of range Exception", because whenever it reaches the end of the list, this value (infinite) will never be lower, thus the Dice "i", or "j" for this case, will not exceed the limit.

That is, if you want to solve the same way, you need to use the same strategy, unless you prefer to do otherwise, example:

i=j=k=0
while i<len(L) and j<len(R):
    if L[i]<R[j]:
        arr[k]=L[i]
        i+=1
    elif R[j]<L[i]:
        arr[k]=R[j]
        j+=1
    k+=1
#Essa parte adiciona os elementos que sobraram
while j<len(R):
    arr[k]=R[j]
    j+=1
    k+=1
while i<len(L):
    arr[k] = L[i]
    i+=1
    k+=1

A good explanation of this method can be found here: https://www.geeksforgeeks.org/merge-sort/

Note: In your iteration, you do not need to create the "tmp" variable, because the "arr" list is a list of integers, the integers are immutable, so you can simply: L.append(a[1])