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]

manual merge sort

# Python program for implementation of MergeSort
def mergeSort(arr):
    if len(arr) > 1:
 
         # Finding the mid of the array
        mid = len(arr)//2
 
        # Dividing the array elements
        L = arr[:mid]
 
        # into 2 halves
        R = arr[mid:]
 
        # Sorting the first half
        mergeSort(L)
 
        # Sorting the second half
        mergeSort(R)
 
        i = j = k = 0
 
        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
 
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
 
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
 
# Code to print the list
 
 
def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()
 
 
# Driver Code
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    print("Given array is", end="
")
    printList(arr)
    mergeSort(arr)
    print("Sorted array is: ", end="
")
    printList(arr)
 
# This code is contributed by Mayank Khanna