**Table of Contents**show

Merge sort is a sorting technique based on divide and conquer methodology

Idea

Sorts a given array A[0..n-1] by dividing it into two halves A[0..(n//2)-1] and A[(n//2) â€¦ (n-1)], sorting each of them recursively and then merging two smaller sorted arrays into a single sorted one.

## Program

```
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
# create temp arrays
L = [0] * (n1)
R = [0] * (n2)
# Copy data to temp arrays L[] and R[]
for i in range(0 , n1):
L[i] = arr[l + i]
for j in range(0 , n2):
R[j] = arr[m + 1 + j]
# Merge the temp arrays back into arr[l..r]
i = 0 # Initial index of first subarray
j = 0 # Initial index of second subarray
k = l # Initial index of merged subarray
while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L[], if there
# are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if there
# are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
if l < r:
# Same as (l+r)//2, but avoids overflow for
# large l and h
m = (l+(r-1))//2
# Sort first and second halves
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
#Get the elements from user
n = int(input("Enter the number of elements:"))
A=[]
print("Enter the elements:")
for i in range(n):
A.append(int(input()))
mergeSort(A,0,len(A)-1)
print("Sorted Array:")
for i in range(n):
print("At index",i,"the element is:",A[i])
```

**Output**

```
Enter the number of elements:5
Enter the elements:
21
-1
-2
4
3
Sorted Array:
At index 0 the element is: -2
At index 1 the element is: -1
At index 2 the element is: 3
At index 3 the element is: 4
At index 4 the element is: 21
```

**Example**

**Splitting**

**Merging**

Views: 0