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
# a variável m desse código representa meio da lista # create two empty arrays L[0..nL] and R[0..nR] L =  * (nL + 1) R =  * (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]
# 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)
nR split the list in half and half, does the way I write it result in a different list than the correct code?
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 =  * (nL + 1) R =  * (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)