# 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 newly 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]

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