下面资料来源：http://blog.csdn.net/chenhuajie123/article/details/9296359
归并排序的定义
归并排序算法采用的是分治算法,即把两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.注意:归并排序的一种稳定排序,即相等元素的顺序不会改变.
归并排序的原理
常见的排序主要有两种,一种是先把待排序的序列一次分割,使子序列的长度减小至1,然后在合并,另外一种是把待排序两两分组排序然后在合并,具体过程用图来解释:
(1) 先分割再合并
待排序序列(14,12,15,13,11,16)
(2) 分组合并
待排序序列(25,57,48,37,12,92,86)
(图片显示不了，无语，有空画一个。)
归并排序实现的示例代码:
归并排序的时间复杂度
归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。
==========================================================
来源：http://xwrwc.blog.163.com/blog/static/46320003201141582544245/
1》归并排序的步骤如下：
Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
Conquer: 对这两个子序列分别采用归并排序。
Combine: 将两个排序好的子序列合并成一个最终的排序序列。
2》时间复杂度：
这样计算出的结果应该是T(n)的上界。下面我们把T(n/2)展开成2T(n/4)+cn/2（下图中的(c)），然后再把T(n/4)进一步展开，直到最后全部变成T(1)=c（下图中的(d)）：
把图(d)中所有的项加起来就是总的执行时间。这是一个树状结构，每一层的和都是cn，共有lgn+1层，因此总的执行时间是cnlgn+cn，相比nlgn来说，cn项可以忽略，因此T(n)的上界是Θ(nlgn)。
如果先前取c1和c2中较小的一个设为c，计算出的结果应该是T(n)的下界，然而推导过程一样，结果也是Θ(nlgn)。既然T(n)的上下界都是Θ(nlgn)，显然T(n)就是Θ(nlgn)。
========================================================
来源：http://learn.akae.cn/media/ch11s04.html
Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
Conquer: 对这两个子序列分别采用归并排序。
Combine: 将两个排序好的子序列合并成一个最终的排序序列。
在描述归并排序的步骤时又调用了归并排序本身，可见这是一个递归的过程。
例 11.2. 归并排序
View Code
<code>sort</code>函数把a[start..end]平均分成两个子序列，分别是a[start..mid]和a[mid+1..end]，对这两个子序列分别递归调用<code>sort</code>函数进行排序，然后调用<code>merge</code>函数将排好序的两个子序列合并起来，由于两个子序列都已经排好序了，合并的过程很简单，每次循环取两个子序列中最小的元素进行比较，将较小的元素取出放到最终的排序序列中，如果其中一个子序列的元素已取完，就把另一个子序列剩下的元素都放到最终的排序序列中。为了便于理解程序，我在<code>sort</code>函数开头和结尾插了打印语句，可以看出调用过程是这样的：
图 11.4. 归并排序调用过程
首先分析<code>merge</code>函数的时间复杂度。在<code>merge</code>函数中演示了C99的新特性－－可变长数组，当然也可以避免使用这一特性，比如把<code>left</code>和<code>right</code>都按最大长度<code>LEN</code>分配。不管用哪种办法，定义数组并分配存储空间的执行时间都可以看作常数，与数组的长度无关，常数用Θ-notation记作Θ(1)。设子序列a[start..mid]的长度为<code>n1</code>，子序列[mid+1..end]的长度为<code>n2</code>，a[start..end]的总长度为n=n1+n2，则前两个<code>for</code>循环的执行时间是Θ(n1+n2)，也就是Θ(n)，后面三个<code>for</code>循环合在一起看，每走一次循环就会在最终的排序序列中确定一个元素，最终的排序序列共有n个元素，所以执行时间也是Θ(n)。两个Θ(n)再加上若干常数项，<code>merge</code>函数总的执行时间仍是Θ(n)，其中n=end-start+1。
然后分析<code>sort</code>函数的时间复杂度，当输入长度n=1，也就是<code>start==end</code>时，<code>if</code>条件不成立，执行时间为常数Θ(1)，当输入长度n>1时：
总的执行时间 = 2 × 输入长度为n/2的<code>sort</code>函数的执行时间 + <code>merge</code>函数的执行时间Θ(n)
设输入长度为n的<code>sort</code>函数的执行时间为T(n)，综上所述：
如果先前取c1和c2中较小的一个设为c，计算出的结果应该是T(n)的下界，然而推导过程一样，结果也是Θ(nlgn)。既然T(n)的上下界都是Θ(nlgn)，显然T(n)就是Θ(nlgn)。
和插入排序的平均情况相比归并排序更快一些，虽然<code>merge</code>函数的步骤较多，引入了较大的常数、系数和低次项，但是对于较大的输入长度n，这些都不是主要因素，归并排序的时间复杂度是Θ(nlgn)，而插入排序的平均情况是Θ(n2)，这就决定了归并排序是更快的算法。但是不是任何情况下归并排序都优于插入排序呢？哪些情况适用插入排序而不适用归并排序？留给读者思考。
快速排序是另外一种采用分而治之策略的排序算法，在平均情况下的时间复杂度也是Θ(nlgn)，但比归并排序有更小的时间常数。它的基本思想是这样的：
下面来自百度百科：http://baike.baidu.com/link?url=ctLPkJAC2f8htsbT_S_HWB_2_5wRxEQ3QFXpiUWVnl-SC-8kLqZQQRVhL73AVsE0#3_2
快速排序算法
过程就不复制了。看代码吧
下面是Java快排的代码：
其他关于快排的讲解：
http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html