Mergesort Implementation gone wrong

Question

Output not as expected

import random

def mergeSort(a):

    width = 1
    n = len(a)                                        

    while (width < n):

        l = 0
        while (l < n):
            r = min(l + (width * 2 - 1), n - 1)
            m = (l + r) // 2

            if (width > n // 2):    
                m = r - ( n % width)
            merge(a, l, m, r)
            l += width * 2

        width *= 2
    return a


def merge(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]

    i = 0
    j = 0
    k = l
    while (i < n1) and (j < n2):
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


def create_random_list(n):
    L = []
    for _ in range(n):
        L.append(random.randint(1,n))
    return L

a = create_random_list(100)
print("Given array is ")
print(a)

mergeSort(a)

print("Sorted array is ")
print(a)```

output

Given array is [54, 17, 12, 61, 54, 13, 42, 82, 14, 65, 72, 11, 38, 76, 75, 56, 30, 1, 48, 52, 49, 88, 62, 94, 37, 98, 99, 79, 2, 77, 16, 67, 94, 14, 11, 24, 25, 20, 55, 92, 83, 85, 99, 50, 93, 49, 91, 73, 24, 84, 68, 21, 100, 4, 54, 65, 43, 74, 43, 60, 9, 27, 68, 15, 71, 39, 19, 69, 87, 56, 63, 56, 56, 70, 1, 51, 4, 87, 84, 7, 92, 30, 97, 74, 34, 45, 89, 33, 13, 41, 14, 92, 46, 8, 28, 72, 72, 37, 34, 64]

Sorted array is [1, 1, 2, 4, 4, 7, 8, 9, 11, 11, 12, 13, 13, 14, 14, 14, 15, 16, 17, 19, 20, 21, 24, 24, 25, 27, 28, 30, 30, 33, 34, 37, 38, 39, 41, 42, 43, 43, 45, 46, 48, 49, 49, 50, 51, 52, 54, 54, 54, 55, 56, 56, 56, 56, 60, 61, 62, 63, 65, 65, 67, 68, 68, 69, 70, 71, 72, 72, 73, 74, 74, 75, 76, 77, 79, 82, 83, 84, 84, 85, 87, 87, 88, 89, 91, 92, 92, 92, 93, 94, 94, 97, 34, 37, 64, 72, 98, 99, 99, 100]

Answer 1

In case anyone's interested here's a recursive merge sort implementation. You'll need Python 3.8+

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) >> 1
        mergeSort(left := arr[:mid])
        mergeSort(right := arr[mid:])

        i = j = k = 0

        ll, lr = len(left), len(right)

        while i < ll and j < lr:
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < ll:
            arr[k] = left[i]
            k += 1
            i += 1

        while j < lr:
            arr[k] = right[j]
            k += 1
            j += 1