pythonalgorithmsortingdata-structures

Efficient Merge sort implementation in python


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)
    
    

    Prints

    [0, 1, 2, 2, 4, 4, 5, 22, 33, 44]