Copy and Split a List in Python3, Merge Sort

Question:

I was trying to write merge sort in python on my own, but it returned a list nothing to do with multiple duplicate numbers. When checking the solution code online, I was in doubt about how to create and pass values ​​from one list to another, here is 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)

since nL and nR split the list in half and half, does the way I write it result in a different list than the correct code?

ps: link to correct code

Answer:

I took a look at the code link you gave, your way of writing is also correct but you need 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 a list L and R was created with an extra index, different from what you did, but that has an explanation.

During the code, it is noticed 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 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 iterated, it won't run the risk of suffering an "index out of range exception", because whenever it reaches the end of the list, this (infinite) value will never be smaller, thus the index " i", or "j" for this case, will not exceed the limit.

That is, if you want to solve in the same way, you need to use the same strategy, unless you prefer to do it differently, for 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 don't need to create the variable "tmp", as the list "arr" is a list of integers, the integers are immutable, so you can simply: L.append(a[1])

Post Views: 0
Scroll to Top