#
#  Basic idea behind this solution: we have two counters, i and j, which
#  move through list 1 and list 2 respectively.  Each time through the
#  first loop, we identify which counter, i or j, is referencing the smaller
#  item, and append it to the result.
#
#  When the first loop ends, either i or j will not yet be at the end of 
#  the list.  The body of only one of the last 2 loops will execute,
#  depending whether it is i or j that didn't reach the length of its list.
#
#  Note that this is harder than anything that will appear on the final
#  exam, not because the code is too complex, but because the concept
#  of merging two sorted lists isn't entirely obvious, and when we didn't
#  look at it in class, it would not reasonable to expect you to 
#  recognize it during an exam.
#
def merge(list1, list2):
  i = 0
  j = 0
  result = []

  while i < len(list1) and j < len(list2):
    if list1[i] < list2[j]:
      result.append(list1[i])
      i = i + 1
    else:
      result.append(list2[j])
      j = j + 1

  while i < len(list1):
    result.append(list1[i])
    i = i + 1

  while j < len(list2):
    result.append(list2[j])
    j = j + 1

  return result