归并排序  
可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。
    
假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。
  把这种排序算法与I n s e r t i o n S o r t（见程序2 - 1 5）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。
  然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x（见程序1 - 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见程序2 - 7）的递归算法。  
假如用冒泡过程（见程序2 - 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见程序2 - 9）的递归算法。
  这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2 )（见例2 - 1 6和2 - 1 7）。  
上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素，而B仅含一个元素。
  下面来看一看采用平衡分割法会发生什么情况： A集合中含有n/k 个元素，B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并（ m e rg e）的过程，将已排好序的A和B合并成一个集合。  
例2-5 考虑8个元素，值分别为[ 1 0，4，6，3，8，2，5，7 ]。
  如果选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。
  
  元素2比3更小，被移到结果序列；3与5进行比较，3被移入结果序列；4与5比较，4被放入结果序列；5和6比较，。。如果选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6&n。