Suppose there are 2 ordered l1, l2, how to merge the 2 lists more efficiently and keep the ordered state, here the default ordering is positive.
The idea is relatively simple, nothing more than comparing the first element of the head of l1 and l2 in turn, placing the smaller one in a new list, and so on, until all the elements have been placed in a new list.
Consider 2 lists l1 = [2], l2 = [1], how to merge them? (Note: the following implementation will change the original values of l1 and l2)
Copy Code The code is as follows.
def signle_merge_sort(l1, l2):
tmp = []
if l1[0] < l2[0]:
(l1[0])
(l2)
del l2[0]
else:
(l2[0])
(l1)
del l1[0]
return tmp
This really only handles the one element scenario and doesn't solve the problem yet, but at least we have a general idea. If there are 2 elements in the list, the above method won't work. We need to solve the boundary judgment problem, i.e. when one of l1 or l2 is empty, add the remaining one list to the end of the sort result. Then make sure that the function handles only one element per call, solving the problem by recursion.
Copy Code The code is as follows.
def recursion_merge_sort1(l1, l2):
tmp = []
if len(l1) == 0:
(l2)
return tmp
elif len(l2) == 0:
(l1)
return tmp
else:
if l1[0] < l2[0]:
(l1[0])
del l1[0]
else:
(l2[0])
del l2[0]
tmp += recursion_merge_sort1(l1, l2)
return tmp
The above program has 2 problems: too many if-judgments; and initializing tmp every time, which doesn't seem to be very friendly to memory usage. Considering that the program terminates when one of l1 or l2 is empty, it could be rewritten slightly:
Copy Code The code is as follows.
def _recursion_merge_sort2(l1, l2, tmp):
if len(l1) == 0 or len(l2) == 0:
(l1)
(l2)
return tmp
else:
if l1[0] < l2[0]:
(l1[0])
del l1[0]
else:
(l2[0])
del l2[0]
return _recursion_merge_sort2(l1, l2, tmp)
def recursion_merge_sort2(l1, l2):
return _recursion_merge_sort2(l1, l2, [])
But for Python, even tail recursion isn't that efficient, and to avoid blowing up the stack, it's usually still done with a loop, rewritten a little bit more: the
Copy Code The code is as follows.
def loop_merge_sort(l1, l2):
tmp = []
while len(l1) > 0 and len(l2) > 0:
if l1[0] < l2[0]:
(l1[0])
del l1[0]
else:
(l2[0])
del l2[0]
(l1)
(l2)
return tmp
Planted a hole today, reflect on it, that's all.