# Program for Merge Sort using Python

## 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 =  * (temp1)
right =  * (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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.