# Program to implement merge sort in Python

In the python programming article, we are going to learn

- program to implement merge sort in python

###
**Program to implement merge sort in Python**

The program to implement merge sort is as follows:

```
# Owner : TutorialsInhand Author : Devjeet Roy
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
Left = [0] * (n1)
Right = [0] * (n2)
for i in range(0 , n1):
Left[i] = arr[l + i]
for j in range(0 , n2):
Right[j] = arr[m + 1 + j]
i = j = 0
k = l
while i < n1 and j < n2 :
if Left[i] <= Right[j]:
arr[k] = Left[i]
i += 1
else:
arr[k] = Right[j]
j += 1
k += 1
while i < n1:
arr[k] = Left[i]
i += 1
k += 1
while j < n2:
arr[k] = Right[j]
j += 1
k += 1
def merge_sort(arr,l,r):
if l < r:
m = (l+(r-1))//2
merge_sort(arr, l, m)
merge_sort(arr, m+1, r)
merge(arr, l, m, r)
return arr
if __name__ == "__main__":
marks = [22,66,43,58,98,42,77,56,66]
result = merge_sort(marks,0,len(marks)-1)
print("The sorted marks: ", result)
```

The output of the program is as follows:

```
PS C:\Users\DEVJEET\Desktop\tutorialsInHand> python code.py
The sorted marks: [22, 42, 43, 56, 58, 66, 66, 77, 98]
```

###
**Few important tips about the proram**

1. Merge sort follows divide and conquer paradigm of problem solving.

2. It splits the input list into two halves, repeating the process on those halves and then finally merging the two sorted halves.

3. The time complxity of the the algorithm is O(nlogn).

Would you like to see your article here on tutorialsinhand.
Join

*Write4Us*program by tutorialsinhand.com**About the Author**

**Devjeet Roy**

Full Stack Web Developer & Blockchain Enthusiast

Page Views :

**Published Date :****Oct 13,2022**
Please Share this page