Table of Contents
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.
0 Comments