Untitled

def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    # Create temporary array for the smaller half
    if n1 <= n2:
        temp = [0] * n1
    else:
        temp = [0] * n2

    for i in range(n1):
        temp[i] = arr[left + i]

    i = 0
    j = mid + 1
    k = left

    while i < n1 and j <= right:
        if temp[i] <= arr[j]:
            arr[k] = temp[i]
            i += 1
        else:
            arr[k] = arr[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = temp[i]
        i += 1
        k += 1

def merge_sort(arr, left, right):
    if left < right:
        mid = left + (right - left) // 2
        merge_sort(arr, left, mid)
        merge_sort(arr, mid + 1, right)
        merge(arr, left, mid, right)

def custom_merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        custom_merge_sort(left_half)
        custom_merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Test Case 1: {3, 7, 9} and {}
arr1 = [3, 7, 9]
custom_merge_sort(arr1)
print(arr1)  # Output: [3, 7, 9]

# Test Case 2: {2, 7, 9} and {1}
arr2 = [2, 7, 9, 1]
custom_merge_sort(arr2)
print(arr2)  # Output: [1, 2, 7, 9]

# Test Case 3: {1, 7, 10, 15} and {3, 8, 12, 18}
arr3 = [1, 7, 10, 15, 3, 8, 12, 18]
custom_merge_sort(arr3)
print(arr3)  # Output: [1, 3, 7, 8, 10, 12, 15, 18]

# Test Case 4: {1, 3, 5, 5, 15, 18, 21} and {5, 5, 6, 8, 10, 12, 16, 17, 17, 20, 25, 28}
arr4 = [1, 3, 5, 5, 15, 18, 21, 5, 5, 6, 8, 10, 12, 16, 17, 17, 20, 25, 28]
custom_merge_sort(arr4)
print(arr4)  # Output: [1, 3, 5, 5, 5, 5, 6, 8, 10, 12, 15, 16, 17, 17, 18, 20, 21, 25, 28]