PYTHON

merge sort function

def merge_sort(arr):
    """Execute the merge sort algorithm"""
    if len(arr) > 1:
        # recursive case
        mid = len(arr) // 2 # find the midpoint of the array
        l = arr[:mid] # define the left half of the array
        r = arr[mid:] # define the right half of the array

        l = merge_sort(l) # sort the left half by calling this function
        r = merge_sort(r) # sort the right half by calling this function

        # now merge the two lists
        merged = [] # define an empty merged array
        while len(l) > 0 and len(r) > 0:
            # compare the heads of the left and right array
            if l[0] <= r[0]:
                # if the head of the left list is smaller than the head of the right list
                # pop the head of the left list and append it to the merged list
                merged.append(l.pop(0))
            else:
                # otherwise, pop the head of the right list and append that
                merged.append(r.pop(0))

        # add any elements remaining in the left or right list to the merged list
        merged = merged + l + r

        return merged
    else:
        # base case
        return arr

sorting merge

# Merge Sorting:

def merge(a,b):
    merged_list = []
    len_a,len_b = len(a),len(b)
    index_a,index_b = 0,0

    while index_a < len_a and index_b < len_b:
        if a[index_a] < b[index_b]:
            merged_list.append(a[index_a])
            index_a += 1
        else:
            merged_list.append(b[index_b])
            index_b += 1

    if index_a < len_a:
        merged_list.extend(a[index_a:])
    elif index_b < len_b:
        merged_list.extend(b[index_b:])
    return merged_list

# Now merge sorting:
def merge_sort(L):
    if len(L) <= 1:
        return L
    mid = len(L)//2
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    return merge(left,right)

# input list:
L = [[4,7,2,3],[10],[10,9,8,7,6],[2,3,1],[1,2],[2,1]]
total_sorted_list = []
for i in L:
    sorted_list = merge_sort(i)
    print("Original List:",i)
    print("Sorted List:",sorted_list)
    print()

# Output:
Original List: [4, 7, 2, 3]
Sorted List: [2, 3, 4, 7]

Original List: [10]
Sorted List: [10]

Original List: [10, 9, 8, 7, 6]
Sorted List: [6, 7, 8, 9, 10]

Original List: [2, 3, 1]
Sorted List: [1, 2, 3]

Original List: [1, 2]
Sorted List: [1, 2]

Original List: [2, 1]
Sorted List: [1, 2]