merge_sort

#! /usr/bin/python

import random

def sort_sublist (sort_list):										#insertion sort
	"Sorts the sub lists using insertion sort"
	for j in range(1,len(sort_list)):
		key = sort_list[j]									#compare with next
		i = j - 1
		while i >= 0 and sort_list[i] > key:						#compare the key with the its left elements...if smaller swap
			sort_list[i+1] = sort_list[i]							#swapping
			i = i - 1										#move left
		sort_list[i+1] = key									#swapping
	print "The sorted list : ",sort_list
	return sort_list

list = []
left = []
right = []

sentinal = 999

for i in xrange(10):
	list.append(random.randrange(1,100,1))					#generate a list of ten random numbers between 1 and 100
print "The List : ",list

n = len(list)/2

for i in range(0,n):
	left.append(list[i])
left.append(sentinal)

#print "Left list : ",left
left = sort_sublist(left)

for i in range(n,len(list)):
	right.append(list[i])
right.append(sentinal)
	
#print "Right list : ",right
right = sort_sublist(right)

i = 0 ; j = 0

for k in xrange(10):
	if left[i] <= right[j]:
		list[k] = left[i]
		print "i =",i
		i = i + 1
	else:
		list[k] = right[j]
		print "j =",j
		j = j + 1 
print list