# Merge Sort Algorithm in Python

Merge sort is a divide and conquer algorithm that works as follows..

• If the length of the given list is more than 1, divide it into n sublists using recursion, each containing 1 element because a list containing 1 element is always sorted.
• Again using recursion, repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. The final list will be the sorted list.

The python code for the merge sort is as follows…

``````def merge_list(s,l1,l2):
i = 0
j = 0
k = 0
# this loop will make sure one of the lists reaches to the end and then
# subsequent while loop will just append the remaining elements from
# the other list
while (i < len(l1) and j < len(l2)):
if (l1[i] < l2[j]):
s[k] = l1[i]	# s is the sorted list
i = i+1
else:
s[k] = l2[j]
j = j+1
k = k+1
# append the remaining elements of the list l1
while (i < len(l1)):
s[k] = l1[i]
i = i+1
k=k+1
# append the remaining elements of the list l2
while (j < len(l2)):
s[k] = l2[j]
j = j+1
k=k+1
return s

def merge_sort(a):
n = len(a)
if (n == 1):
return a
else:
mid = n//2		# create two sublists
l1 = a[:mid]
l2 = a[mid:]
merge_sort(l1)
merge_sort(l2)
sorted_list = merge_list(a,l1,l2)
return sorted_list

l = [13,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
final = merge_sort(l)
print "sorted list is ",final``````

The output of the above program looks like this…

sorted list is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 18]

## One Reply to “Merge Sort Algorithm in Python”

1. FirstFelicitas says:

I see you don’t monetize your page, don’t waste your traffic, you can earn extra bucks
every month because you’ve got high quality content.
If you want to know how to make extra \$\$\$, search for: