合并排序
考虑两个有序的数组，我们如何将它合并成第三个有序的数组？
比如：
a=[1, 3, 5, 7]
b=[2,4,4 ]
分用左手和右手从a,b数组中拿出元素，如果左手的小，就放第三个有序数组中去，反之，就把右手的放到第三个数组中，然后用空着的手取下一个：
------------
1357
↓取a1
1
244
------------
357
1 2
↑取b2
244
---------
357
↓取a2
123
44
--------
57
1234
↑取b2
44
----------
57
12344
↑ 取b3
4
----------
5 7
↓ ↓取a3a4
123445 7
这样，就可以将两个有序数组合成一个有序数组。
让我考虑更多的情况：
A1:考虑 1个元素的数组，本身为已序。
A2:两个元素的数组，可以看为将两个分别含有1个元素的数组合并成第三个已序的数组。
A3:可以归结为A2+A1的过程，然后再合并一次。
A4:归结为A2+A2的过程，然后再合并一次。
。。。
对于An,我们可以将它看作两个分别是两个A(n/2)合并一次的过程。
这就是我们所说的合并排序。
合并排序是所说的分治法，分治法一般要3步：
1，分解，将问题n分解为 两个 n/2 直到我们能直接解决的数。
2，解决问题。
3，合并，将分解以后的问题。
看图演示一个合并排序过程：
代码就是明显的递归模式了。
import randomdef merge(a, left, right , end): ''' merge two sorted sequence left right end of merge(Not include) a[left:right] a[right:end] ''' llen=right - left rlen=end - right al=a[left:right] al.append(None) ar=a[right:end] ar.append(None) l=0 r=0 #print '<',left,right,end #print 'lr', al,ar #print a for i in range(end - left): if al[l] != None and ar[r] != None and (al[l] <= ar[r]): a[left+i] = al[l] l=l+1 elif al[l] != None and ar[r] != None : a[left+i] = ar[r] r=r+1 elif ar[r] == None and al[l] != None:#right array is empty a[left+i:end] = al[l:right-left] break elif al[l] == None and ar[r] != None: a[left+i:end] = ar[r:end-right] break return adef merge_sort(a,s,e): ''' array [s:e+1]python slice [) ''' if s < e: m=(s+e)/2 merge_sort(a, s, m ) #a[s:m+1]python slice [) merge_sort(a, m+1 , e)#a[m+1:e][m+1:e+1] python slice [) merge(a, s,m+1,e+1) return afor x in range(10000): a=[] b=list() n=random.randint(100,1130) for i in range(1000): b.append(i) for i in range(n): #choose 9 random numbers in (1...1000) as a sort list a.append( random.choice(b)) b= merge_sort(a,0,n-1) if b!= sorted(a): print 'err',n, x print a print b print sorted(a)#a=[0, 177, 911, 453, 566, 985]#print merge_sort(a,0,5)#print merge(a,0,3,6)#print a
画图使用gravpviz的dot,源代码如下：
digraph merge{ charset="utf-8"; node [shape=plaintext, fontsize=16]; "寮€濮?quot;->"鍒嗚В"->"鎺掑簭"->"鍚堝苟"; node [shape=box ,rotate=90 ]; node [ width=3 ]; {rank =same;"5 2 4 7 1 3 6 2"; "寮€濮?quot;;} node [ width=1.5 ]; "5 2 4 7 1 3 6 2"->"5 2 4 7"; "5 2 4 7 1 3 6 2"->"1 3 6 2"; {rank = same;"5 2 4 7";"1 3 6 2"; } node [ width=.75 ]; {rank = sname;"5 2"; "4 7";"1 3"; "6 2";} "5 2 4 7" -> "5 2"; "5 2 4 7" -> "4 7"; "1 3 6 2" ->"1 3"; "1 3 6 2" ->"6 2"; { rank = same; "5";"2";"4";"7";"1";"3";"6";"2 ";"鍒嗚В";} "5 2"->5; "5 2"->2; "4 7"->4; "4 7"->7; "1 3"->1; "1 3"->3; "6 2"->"6"; "6 2"->"2 "; { rank = same; "2 5";"4 7";"1 3"; "2 6";"鎺掑簭";} 5->"2 5"; 2->"2 5"; 4->"4 7"; 7->"4 7"; 1->"1 3"; 3->"1 3"; "6"-> "2 6"; "2 "-> "2 6"; node [ width=1.5 ]; {rank = same; "2 4 5 7"; "1 2 3 6";} "2 5"->"2 4 5 7"; "4 7"->"2 4 5 7"; "1 3"-> "1 2 3 6"; "2 6"->"1 2 3 6"; node [ width=3 ]; "2 4 5 7" -> "1 2 2 3 4 5 6 7"; "1 2 3 6" -> "1 2 2 3 4 5 6 7"; {rank=same;"1 2 2 3 4 5 6 7";"鍚堝苟";} }
分治法使用递归，递归的讨论放到一篇里讨论。
