What is the best way to merge two lists?

[Rob Renaud]

I think this works... I don't know if the ability to sort (hence,
objects must be comparable), breaks your guarentee, but my algorithm
should be O(n*lg(n)) I believe, while yours is O(n*n).  I am also not
a great python programmer (read, I suck with python and my C++
background is probably extremely evident :) ).  But anyway, here it
is, along with a little bit of benchmarks.

If this fits your requirements and you want to know how it works and
can't understand from the code, I'll try to explain it.

import time

def merge(*lists):
	sorted_combo = []
	for single_list in lists:
		sorted_combo += single_list
	sorted_combo.sort()

	uniq_count = 0
	current = 0
	uniq_tracker = [None]*len(sorted_combo)
	upper_bound = len(sorted_combo) - 1

	if upper_bound == -1: # special case, all lists are empty
		return []

	while current < upper_bound:
		if sorted_combo[current] != sorted_combo[current+1]:
			uniq_tracker[current] = 1
			uniq_count += 1
		current += 1

	# last element always unique
	uniq_count += 1
	uniq_tracker[-1] = 1

	result = [None]*uniq_count
	index_to_check = 0
	index_to_add = 0
	for elem in sorted_combo:
		if uniq_tracker[index_to_check] != None:
			result[index_to_add] = elem
			index_to_add += 1
		index_to_check += 1

	return result

def uniq(*args) :
    theInputList = []
    for theList in args:
       theInputList += theList
    theFinalList = []
    for elem in theInputList:
       if elem not in theFinalList:
          theFinalList.append(elem)
    return theFinalList

def time_test(func, lists):
	total_items = 0
	for single_list in lists:
		total_items += len(single_list)
	start = time.time()
	func(*lists)
	elapsed = time.time() - start
	print ("%s took %f seconds to merge %d lists of %d total elements") %
(
	func.__name__, elapsed, len(lists), total_items)

test_lists = [range(12325), range(1234), ['hello', 'my name is rob']]
time_test(uniq, test_lists)
time_test(merge, test_lists)