Efficient Merge sort implementation in python

July 1, 2024

def merge(arr, l, m, r):
    merged_arr = []
    i, j = 0, 0
    while (i < len(arr[l:m])) and (j < len(arr[m:r+1])):
        if arr[l+i] < arr[m+j]:
            merged_arr.append(arr[l+i])
            i += 1
        elif arr[l+i] >= arr[m+j]:
            merged_arr.append(arr[m+j])
            j += 1
    merged_arr.extend(arr[m+j:r+1])
    merged_arr.extend(arr[l+i:m])
    arr[l:r+1] = merged_arr
    return

def merge_sort(arr, l, r):
    if r > l:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m+1, r)
        return merge(arr, l, m, r)

I am not sure what is wrong with my merge function. The following works well:
print(merge([1,4,7,8,9,20, 0,4,5,15,67,68], 0, 6,12))
However, this does not give correct output:
print(merge_sort([1, 5, 4, 2, 33, 4, 2, 44, 22, 0], 0, 10))

>Solution :

The end index for slicing is not inclusive:

def merge(arr, l, m, r):
    L, R, i, j = arr[l:m], arr[m:r], 0, 0
    merged_arr = []
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            merged_arr.append(L[i])
            i += 1
        else:
            merged_arr.append(R[j])
            j += 1
    merged_arr.extend(L[i:])
    merged_arr.extend(R[j:])
    arr[l:r] = merged_arr


def merge_sort(arr, l, r):
    if r - l > 1:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m, r)
        merge(arr, l, m, r)


A = [1, 5, 4, 2, 33, 4, 2, 44, 22, 0]
merge_sort(A, 0, len(A))
print(A)