CODEWITHSUNDEEP
pythonsortingrecursionmergesort
Chinnmay B S
Chinnmay B S

Reputation: 115

Issue with merge sort

I'm trying to run merge sort using python and recursion it is working fine for some cases not not working fine for most of the cases please correct me I tried and unable to find error in code.

def merge_sort(a, min, max):
    if max - min < 2:
        return a[min:max]

    mid = (min + max) // 2
    L = merge_sort(a, min, mid)
    R = merge_sort(a, mid, max)
    return (sort(L, R))

def sort(L, R):
    (c, m, n) = ([], len(L), len(R))
    (i, j) = (0, 0)
    while (i + j < m + n):
        if i == m:
            c.append(R[j])
            j += 1
        elif j == m:
            c.append(L[i])
            i += 1
        elif R[j] <= L[i]:
            c.append(R[j])
            j += 1
        elif L[i] < R[j]:
            c.append(L[i])
            i += 1
    return c

Upvotes: 1

Views: 73

Answers (1)

Will Ness
Will Ness

Reputation: 71075

You have a typo there, it should be j==n in the second case.

Next one is not an error, but it is usual to prefer the equal element coming from the left argument over the one on the right, for the sort to be stable (not change the order of elements unnecessarily). So you also need to switch the <= and the < comparisons in the other two cases.

Naming is also important. The sort function is really sorted_merge.

Upvotes: 1

Related Questions