This is not an assignment, but it is related to my Data Structures class.
I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + list2. I still want to know the answer for my question - it seemed important to my professor that we learn how to write good recursive function. The time complexity of a well written recursive merge function, according to him, is O(n).
The function receives two ordered lists and merges them into another ordered list. I would say that it runs in O(n), but, at the same time, I feel that my function is not well written; I guess I can't evaluate this more precisely because I don't quite know everything that happens behind the scenes to the Python's built-in functions I use.
def mergeR(l1, l2): lfinal =  if not l1: return l2 if not l2: return l1 if l1 < l2: lfinal.append(l1.pop(0)) elif l1 == l2: l2.pop(0) else: lfinal.append(l2.pop(0)) lfinal.extend(mergeR(l1, l2)) return lfinal