I am trying merge with a different type, and I am unable to get the correct output. I just want to pass the list in the final function and get the sorted output. Can anyone please guide me where I am wrong??
def merge(arr, start, mer1, mer2, end):
left_array = arr[start - 1 : mer1]
mid_array = arr[mer1: mer2 + 1]
right_array = arr[mer2 + 1 : end]
left_array.append(float('inf'))
mid_array.append(float('inf'))
right_array.append(float('inf'))
ind_left = 0
ind_mid = 0
ind_right = 0
for i in range(start - 1, end):
minimum = min([left_array[ind_left], mid_array[ind_mid], right_array[ind_right]])
if minimum == left_array[ind_left]:
arr[i] = left_array[ind_left]
ind_left += 1
elif minimum == mid_array[ind_mid]:
arr[i] = mid_array[ind_mid]
ind_mid += 1
else:
arr[i] = right_array[ind_right]
ind_right += 1
def merge_sort(L, start = None, end = None):
start = start or 1
end = end or (len(L) - 1)
if len(L[start - 1: end]) < 2:
return L
else:
meg1 = start + ((end - start) // 3)
meg2 = start + 2 * ((end - start) // 3)
merge_sort(L, start, meg1)
merge_sort(L, meg1 + 1, meg2 + 1)
merge_sort(L, meg2 + 2, end)
merge(L, start, meg1, meg2, end)
return L
arr = [312,413,3,423,5,3,342,1,2, 69, 69, 76]
print (merge_sort(arr))
The output I am getting is
[1, 2, 3, 3, 5, 69, 69, 312, 342, 413, 423, 76]
I think you're just computing the wrong initial end position in the second line of your merge_sort function. When I change the line:
end = end or (len(L) - 1)
to:
end = end or len(L)
I get the right result:
[1, 2, 3, 3, 5, 69, 69, 76, 312, 342, 413, 423]