2.合并排序
当需要排序一个集合时，你该怎么做？ 什么？ 你调用 sort()方法…. 好吧，好答案…但是对一个数据库来说，你需要弄明白这个sort()方法是怎么工作的.
这里有几种不错的排序算法，所以我这里重点说说这个最重要的算法：合并排序 你可能现在还不明白为啥对数据进行排序这么重要，在这篇文章后面的章节<查询优化>中会交待。 此外，了解合并排序将有助于我们理解后面的一个常用数据库操作：join ,因为它调用了合并排序
2.1合并
像许多有用的算法一样，合并排序基于一个技巧：将2个大小为N/2的已排序数组合并为N个元素的排序数组仅需要N次操作。 此操作称为合并。
让我们通过一个简单的例子来说明：
从上图上你可以看到，要想得到最终的已经排好序的8元素数组，你只需要迭代一次在两个有序的4元素数组中.
- 比较两个数组的第一个元素(这里要想象一下两个数组都有个游标)
- 然后把最小的那个数放到8元素数组的第一个位置上
- 接着把游标顺着移走的数移到下一个位置上 重复1，2，3 动作，直到到达两个数组其中一个的终点。 然后把另一个数组里剩下的元素都放到8元素结果集中 这个排序的前题是原始的4元素数组是已经排序过的，所以你不需要在数组中做”go back” 操作
现在我们已经明白了合并排序的技巧了，这是我写的合并排序的伪码
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);
//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;
合并排序把问题分解成更小的问题，然后这些通过解决小问题，得到初始问题的结果。(这种算法被称为：分而治之). 如果你不明白这种算法，不要着急，我一开始也不太明白，我们来尝试把这个算法拆成两阶段算法：
- 分隔阶段 把数组分隔成更小的数组
- 排序阶段 把小的数组合并到一起（用合并）成一个大数组
2.2分隔阶段
在上图的例子中，整个分隔阶段,一共用了3个步骤把数组分隔了单一数组 ，计算步骤的公式是 log(N) (这里N=8,long(N)=3)
我是怎么知道这个公式的?
~~我是个天才! ~~ 认真的说，用一个词来概括: 数学. 每一步都将数组的大小除以2. 步骤数就是可以将初始数组除以2的次数.这是个很准确的定义(基于2分法).
2.3排序阶段
在排序阶段, 我们从单一数组开始. 在每一步, 你应用了多次合并，总的花费是N=8次操作:
- 在第一步中，需要合并4次，每次花费2次操作
- 在第二步中，需要合并2次，每次花费4次操作
- 在第三步中，需要合并1次，每次花费8次操作
这里共有log(N)个步骤，这个算法总共需要N*log(N)次操作
合并排序的能力
为什么合并排序如此给力
因为: - 你可以改进它以减少内存占用，通过某种方法，你不需要创建一个新数组而是直接修改原数组。
note:这种算法被称为：in-place(原位操作)
- 你可以改进它以达到同时使用（少量内存+一定的磁盘空间）来完成排序，这并不会得到太多的I/O惩罚。这个技巧是：只加载当前正在处理的数据到内存.当你只有100M的内存排序1000M的数据进行排序时，这一点显得很重要。
note:这种算法被称为：external sorting(外部排序)
你可以改进它以达到多*进程/线程/服务器*运行 举个例子，分布式合并排序是Hadoop的一个关键组件。
这个数法可以点石成金（真的！）
合并算法被大多数（即使不是全部）数据库，但不是唯一的一个。如果你想了解更多，可以去读这篇讨论数据库各种排序算法优缺点的研究论文（http://wwwlgis.informatik.uni-kl.de/archiv/wwwdvs.informatik.uni-kl.de/courses/DBSREAL/SS2005/Vorlesungsunterlagen/Implementing_Sorting.pdf）
本节完成，下一章节我们将讨论：数组.树.哈希表
本篇文章完整分为7节，当前第3节。以下完整章节：