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.