Python对两个有序列表进行合并和排序的例子
假设有2个有序列表l1、l2，如何效率比较高的将2个list合并并保持有序状态，这里默认排序是正序。
思路是比较简单的，无非是依次比较l1和l2头部第一个元素，将比较小的放在一个新的列表中，以此类推，直到所有的元素都被放到新的列表中。
考虑2个列表l1=[2],l2=[1]，如何将他们合并呢？(注意：下面实现会改变l1和l2本来的值)
defsignle_merge_sort(l1,l2):
tmp=[]
ifl1[0]<l2[0]:
tmp.append(l1[0])
tmp.extend(l2)
dell2[0]
else:
tmp.append(l2[0])
tmp.extend(l1)
dell1[0]
returntmp这真的只能处理一个元素的情形，还不能解决问题，不过好歹我们有一个大概的思路了。如果有列表中2个元素，上面的方法就不行了。我们需要解决边界判断问题，即当l1或者l2有一个为空的时，将剩下的一个list加到排序结果的尾部。然后确保函数每次调用只处理一个元素，通过递归来解决问题。
defrecursion_merge_sort1(l1,l2):
tmp=[]
iflen(l1)==0:
tmp.extend(l2)
returntmp
eliflen(l2)==0:
tmp.extend(l1)
returntmp
else:
ifl1[0]<l2[0]:
tmp.append(l1[0])
dell1[0]
else:
tmp.append(l2[0])
dell2[0]
tmp+=recursion_merge_sort1(l1,l2)
returntmp上面的程序有2个问题：if判断太多；每次都要初始化tmp，对内存使用似乎不太友好。考虑到程序在l1或者l2有一个为空的时候就终止，可以稍微改写一下：
def_recursion_merge_sort2(l1,l2,tmp):
iflen(l1)==0orlen(l2)==0:
tmp.extend(l1)
tmp.extend(l2)
returntmp
else:
ifl1[0]<l2[0]:
tmp.append(l1[0])
dell1[0]
else:
tmp.append(l2[0])
dell2[0]
return_recursion_merge_sort2(l1,l2,tmp)
defrecursion_merge_sort2(l1,l2): return_recursion_merge_sort2(l1,l2,[])