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]