## Reminder -- merge sort

# merging function: the merging of two sorted list is the sorted union
# of the two lists.

# same format as merge. It is just the merge function but in an
# iterative fashion. (It permits to run the merge on big list, as
# Python has very limited features concerning recursion...)
def merge_it(comp,l0,l1):
  li = []
  while(l0 != [] and l1 != []):
    if comp(l0[0],l1[0]):
      li = li + [l0[0]]
      l0 = l0[1:]
    else:
      li = li + [l1[0]]
      l1 = l1[1:]
  return li+l0+l1

# same format as mergesort. It is the iterative version of the
# mergesort. See how it is much more elaborated than the simpler
# recursive version.
def mergesort_it(comp,l):
  n = len(l)
  l = map(lambda x: [x],l)
  while n > 1:
    if n % 2 == 1:
      l = l[:-2] + [merge_it(comp,l[-2],l[-1])]
    for i in range(n//2):
      l = l[:i] + [merge_it(comp,l[i],l[i+1])] + l[i+2:]
    n = n//2
  return l[0]
##