Latest
Home » Merge Sort Algorithm in Python

# Merge Sort Algorithm in Python Hello everyone, welcome back to Programming In Python. Here in this post am going to tell you how to implement Merge Sort Algorithm in Python. In the previous posts, I have said about Selection Sort and Bubble Sort, here this Merge sort is much more efficient than those two algorithms as their time complexity is O(n2) in the average case and here it is O(n log n) in the worst case, this says how efficient Merge sort is than Selection and Bubble sort.

Merge sort algorithm is a divide and conquer algorithm, where the main unsorted list is divided into 2 halves, and each of the halves is again divided into 2 halves until only a single element is left in the list. Now merge these sublists by sorting them and finally, the main list is sorted.

You can also watch the video on YouTube here

### July Promo - Limited Time Sale Limited time sale - 50% OFF Learn in-demand data and AI skills on the 17th of July

See the animation below, By Swfung8Own work, CC BY-SA 3.0, Link

### July Promo - Limited Time Sale Limited time sale - 50% OFF Learn in-demand data and AI skills on the 17th of July

#### Time Complexity Of Merge Sort

 Best Case O(n log n) Average Case O(n log n) Worst Case O(n log n)

## Algorithm

1. Divide the unsorted list into n sublists, until each list has only 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

## Program

```__author__ = 'Avinash'

def merge_sort(sort_list):
print("splitting", sort_list)
if len(sort_list) > 1:

mid = len(sort_list) // 2
leftHalf = sort_list[:mid]
rightHalf = sort_list[mid:]

merge_sort(leftHalf)
merge_sort(rightHalf)

i = 0
j = 0
k = 0

while i < len(leftHalf) and j < len(rightHalf):
if leftHalf[i] < rightHalf[j]:
sort_list[k] = leftHalf[i]
i = i + 1
else:
sort_list[k] = rightHalf[j]
j = j + 1
k = k + 1

while i < len(leftHalf):
sort_list[k] = leftHalf[i]
i = i + 1
k = k + 1

while j < len(rightHalf):
sort_list[k] = rightHalf[j]
j = j + 1
k = k + 1

print("merging...", sort_list)

lst = []

size = int(input("Enter size of the list: \t"))

for i in range(size):
elements = int(input("Enter an element: \t"))
lst.append(elements)

merge_sort(lst)```