#!/usr/bin/env python

# merges two sorted lists
# ECS 10, Winter 2012
# Sean Peisert, March 14, 2012

mylist1 = [ -4, 1, 5, 20 ]
mylist2 = [ 0, 3, 6, 8]

# do a selection sort over the list
# parameters: lst, the list of numbers to sort
# returns: nothing
def merge(lst1, lst2):
    # go through each list
    # each (outer) loop puts the smallest number
    # at the head of the list beginning with the
    # given index
	m = len(lst1);
	n = len(lst2);
	lst3 = [0] * (m + n);
    
	i = 0;
	j = 0;
    
	while (i + j < m + n):
    
		if i < m and j < n and lst1[i] <= lst2[j]:
			lst3[i+j] = lst1[i];
			i = i + 1;
			
		elif j < n and i < m and lst1[i] > lst2[j]:
			lst3[i+j] = lst2[j];
			j = j + 1;

		elif i >= m and j != n:
			lst3[i+j] = lst2[j];
			j = j + 1;
			
		elif j >= n and i != m:
			lst3[i+j] = lst1[i];
			i = i + 1;
			
	return lst3;


# this puts it all together
def main():
    # sort and print the list
    mylist3 = merge(mylist1, mylist2);
    print(mylist3);

main()