排序：插入排序和归并排序比较

排序算法的可以用两种不同的标准分类：
1. 存储空间
2. 稳定(stable)

所谓存储空间指的是算法需要的外部空间是不是一个常数。当需要的外部存储空间是常数时，这个排序就是原地排序（in place sort)。反之就不是。计算机科学就是一个时间和空间的妥协，可以用空间换时间，也可以用时间换空间。 所谓稳定，就是相等元素的相对位置不变。例子： 1，3，1，6中两个1的相对位置必须保持一致。

插入排序（Insertion Sort）是算法导论(Introduction to Algorithm)介绍的第一个排序算法，它的优点是算法简洁，实现（implementation）方便，稳定（相同元素的相对位置保持不变），而且是原地排序。缺点是时间复杂度为n²，也就是慢。
归并排序（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倍。

总结：
归并排序是用空间换时间，而插入排序是用时间换空间。