Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Not getting correct output using recursion in python sort because of arguments

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]

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

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]
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading