# Implementation of mergesort with user prompts.
# Copyright (c) 2006 Nick Murdoch.

list = ["Item 1", "Item 2", "Item 3", "..."]


def mergesort(list):
	"""Merge-sorts a list, giving the user prompts
	Returns a list with the user's preferences,
	sorted with their favourites at the end of the list"""
	#print "working on " + str(list)
	length = len(list)
	left = []
	right = []
	if length <= 1:
		return list
	else:
		middle = list[length/2]
		for item in list:
			if item is middle:
				pass
			else:
				try:
					choice = int(raw_input(middle + " or " + item + "? "))
				except ValueError:
					choice = 2
				if choice == 1: # if < middle
					left = left + [item]
				else:			# if > middle
					right = right + [item]
		left = mergesort(left)
		right = mergesort(right)
		return left + [middle] + right
				

print " *** MERGESORT by Nick Murdoch ***"
print "        Copyright (c) 2006\n"
print "Type 1 if you prefer the first film given, or 2 if you prefer the second.\n"

newlist = mergesort(list)

print ""

i = 1
length = len(newlist)
while i <= length:
	print str(i) + ": " + newlist[length - i]
	i = i + 1