Introduction

The task is to sort the given array elements using merge sort. Merge sort is yet another sorting algorithm based on divide and conquer mechanism.

Program

def merge_arr(arr, x, mid, y):
    temp1 = mid - x + 1
    temp2 = y - mid
    left = [0] * (temp1)
    right = [0] * (temp2)
    for i in range(0, temp1):
        left[i] = arr[x + i]
    for j in range(0, temp2):
        right[j] = arr[mid + 1 + j]
    i = 0
    j = 0
    l = x
    while i < temp1 and j < temp2:
        if left[i] <= right[j]:
            arr[i] = left[i]
            i += 1
        else:
            arr[l] = right[j]
            j += 1
        l += 1
    while i < temp1:
        arr[l] = left[i]
        i += 1
        l += 1
    while j < temp2:
        arr[l] = right[j]
        j += 1
        l += 1
def sort(arr, x, y):
    if x < y:
        mid = (x+(y-1))//2
# Sorting two halves
        sort(arr, x, mid)
        sort(arr, mid+1, y)
        merge_arr(arr, x, mid, y)
       
ip_arr = [89, 2, 15, 3]
sort(ip_arr, 0, len(ip_arr) - 1)
print("The sorted array is :")
for i in range(len(ip_arr)):
    print(ip_arr[i])

Output

Explanation

There are two methods: merge_arr() and sort(). The sort() method sorts the two halves of the given array (arr[i…m] and arr[m+1…j) and merge_arr() merges the two halves assuming they are sorted.