1. 存储空间
2. 稳定(stable)
所谓存储空间指的是算法需要的外部空间是不是一个常数。当需要的外部存储空间是常数时，这个排序就是原地排序（in place sort)。反之就不是。计算机科学就是一个时间和空间的妥协，可以用空间换时间，也可以用时间换空间。 所谓稳定，就是相等元素的相对位置不变。例子： 1，3，1，6中两个1的相对位置必须保持一致。
插入排序（Insertion Sort）是算法导论(Introduction to Algorithm)介绍的第一个排序算法，它的优点是算法简洁，实现（implementation）方便，稳定（相同元素的相对位置保持不变），而且是原地排序。缺点是时间复杂度为n2，也就是慢。
归并排序（Merge Sort）则是介绍的第二个算法，优点是快，时间复杂度是nlg(n)，并且稳定。缺点是递归，比插入排序复杂，不是原地排序。
插入排序的算法表述：
把n维数组分成前后两个部分，视前半部分为已排序的(sorted)，后半部分为未排序的(unsorted)。
每次循环取出未排序部分（unsorted）的第一个元素，逐个比较它和已排序部分(sorted)的大小，并且插入到已排序部分（sorted）。
归并排序是一种“分治”（Divide and conquer）算法：把问题(problem)分成若干的小的问题逐个解决。
“分治”算法的三个步骤：
1. 分解（devide）： 将原问题分解为一系列子问题。
2. 解决（conquer）： 递归地解答各个子问题，若子问题够小，可直接求解。
3. 合并(combine）: 将子问题的结果合并成原问题的解。
对于归并排序来说就是：
1. 将n个元素分解为n/2个子序列。
2. 再用归并算法递归解决这两个字序列的问题。
3. 合并两个已排完序的序列。
抽象的数学证明很难给人一个具象的感受，所以需要实验来感受一下。
实验环境：
CPU: Intel Core2 Duo T6400 @ 2.0GHZ
语言： C#(.NET 3.5 SP1) / C++(gcc 3.4.5)
实验数据：
0至100000之间的90000个随机数。
MergeSort(C#):
public static void sort(int[] array)
{
if (array.Length == 2)
{
if (array[0] > array[1])
{
Utility.swap(ref array[0], ref array[1]);
}
return;
}
if (array.Length == 1)
return;
int iMid = array.Length / 2;
int[] first = getArray(array, 0, iMid);
sort(first);
int[] second = getArray(array, iMid, array.Length);
sort(second);
int i = 0, j = 0, k = 0;
for (; j < first.Length && k < second.Length; i++)
{
if (first[j] < second[k])
{
array[i] = first[j];
j++;
}
else
{
array[i] = second[k];
k++;
}
}
if (j != first.Length)
{
for (; j < first.Length; j++, i++)
array[i] = first[j];
}
else
{
for (; k < second.Length; k++, i++)
array[i] = second[k];
}
}
Insertion Sort(C#):
public static void sort(int[] array)
{
int size = array.Length;
for (int i = 1; i < size; i++)
{
for (int j = 0; j < i; j++)
{
if (array[i] < array[j])
{
int v = array[i];
for (int k = i; k > j; k--)
{
array[k] = array[k - 1];
}
array[j] = v;
}
}
}
}
C#结果:
归并排序（merge sort）： 00:00:00.0960054
插入排序（insertion sort）： 00:00:49.5428337
Merge Sort(C++):
template < class T >
void mergeSort(T array[], int const size){
if(size == 2){
if(array[0] > array[1]){
T tmp = array[0];
array[0] = array[1];
array[1] = tmp;
}
return;
}
if(size == 1){
return;
}
int mid = size / 2;
int first_size = mid;
T* first = getArray< T >(array, 0, mid);
mergeSort(first, first_size);
int second_size = size - mid;
T* second = getArray< T >(array, mid, size);
mergeSort(second, second_size);
int i = 0, j = 0, k = 0;
for(; j < first_size && k < second_size;){
if(first[j] < second[k]){
array[i++] = first[j++];
} else {
array[i++] = second[k++];
}
}
while(j != first_size){
array[i++] = first[j++];
}
while(k != second_size){
array[i++] = second[k++];
}
delete [] first;
delete [] second;
}Insertion Sort(C++):
void insertionSort(int array[], int size){
if(array == 0 || size == 0)
return;
for(int i = 1; i < size; i++){
for(int j = 0; j < i; j++){
if(array[i] < array[j]){
int v = array[i];
for(int k = i; k > j; k--){
array[k] = array[k-1];
}
array[j] = v;
}
}
}
}
C++结果(毫秒）：
归并排序（merge sort）： 78
插入排序（insertion sort）： 5273
从实验结果来说，当数据量很大的时候，归并排序的性能（performance）远好于插入排序。
实验同时也表明对于一个好的算法其性能表现比较一致，C#和C++在归并排序的测评上表现相近。但是对一个相对较差的算法来说，更高级的语言似乎会放大这个差距，C++和C#相差10倍。
总结：
归并排序是用空间换时间，而插入排序是用时间换空间。
