Python merging lists -

mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ] import time def timeit(f):     def wrapper(*args, **kw):         t = time.time()         res = f(*args, **kw)         print "%s took %s" % (f.func_name, time.time() - t)         return res      return wrapper  # merge 2 given lists def merge(l, r):     if len(l) == 0:         return r      if len(r) == 0:         return l      if l[0] <= r[0]:         return [l[0]] + merge(l[1:], r)     else:         return [r[0]] + merge(l, r[1:])  def merge2(x,y):     if len(x) == 0:         return y     if len(y) == 0:         return x      #pop lower 1 between 2 biggest items     last = y.pop() if x[-1] < y[-1] else x.pop()      merged = merge2(x,y)     merged.append(last)      return merged  def merge3(xs, ys):     ms = []     = 0     j = 0      while < len(xs) , j < len(ys):         if xs[i] <= ys[j]:             ms.append(xs[i])             = + 1         else:             ms.append(ys[j])             j = j + 1      while < len(xs) , j == len(ys):         ms.append(xs[i])         = + 1      while == len(xs) , j < len(ys):         ms.append(xs[i])         j = j + 1      return ms  # divide , conquer def lmerge(lists, m):     if len(lists) <= 1:         return lists      mid = len(lists) / 2      llists = lmerge(lists[:mid], m)     rlists = lmerge(lists[mid:], m)      # bottom merge have list of list     if isinstance(llists[0], list):         llists = llists[0]     if isinstance(rlists[0], list):         rlists = rlists[0]      return m(llists, rlists)  @timeit def a():     print lmerge(mylists, merge)  @timeit def b():     print lmerge(mylists, merge2)  @timeit def c():     print lmerge(mylists, merge3)  @timeit def d():     print sorted(reduce(lambda x,y: x + y, mylists))   a() b() c() d() 

---

antz@antz-90x3a:~/python/algo$ python addlists.py  [1, 2, 3, 4, 5, 7, 7, 8, 11, 15, 20] [1, 2, 3, 4, 5, 7, 7, 8, 11, 15, 20] took 7.00950622559e-05 [1, 2, 3, 4, 5, 7, 7, 8, 11, 15, 20] b took 6.103515625e-05 traceback (most recent call last):   file "addlists.py", line 101, in <module>     c()   file "addlists.py", line 13, in wrapper     res = f(*args, **kw)   file "addlists.py", line 97, in c     print lmerge(mylists, merge3)   file "addlists.py", line 82, in lmerge     if isinstance(rlists[0], list): indexerror: list index out of range antz@antz-90x3a:~/python/algo$  

kinda confused why raising , index error merge3?

merge, merge2, merge3 should have same output (at least in mind) dont understand why raising indexerror because works merge , merge2

edit: can have better merge algorithm if there one?

unless missed done:

mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ] newlist = [] elem in mylists:     newlist.extend(elem) newlist = sorted(newlist)