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. 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:
    Boorfe’s tips best adsense alternative

Leave a Reply

Your email address will not be published. Required fields are marked *

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