Insertion sort

// insertion sorting
void insertion_sort(int *a, int size)
{
   // the element that want to insert in
   unsigned sofar;
   // elements before sofar
   int prev;
   // saving the value of a[sofar]
   int a_sofar;

   // insertion for each elements
   for (sofar = 1; sofar < size; ++sofar) {
      // save the value of a[sofar]
      a_sofar = a[sofar];
      // previous index start from sofar - 1
      prev = sofar - 1;
      // while previous element is larger then
      // the value that we want to insert, then
      // push it to the right hand side
      while (prev >= 0 && a[prev] > a_sofar) {
         a[prev + 1] = a[prev];
         prev--;
      }
      // then a[prev] is smaller or equal than a_sofar
      // so we can insert a[sofar] to this position
      a[prev+1] = a_sofar;
   }/* sofar */
}

Insertion，插入排序法，是個資料量小時可以做的比較有效率的排序演算法。但是先撇開細部的討論，他的方式就是我們把它想像成身高不同的人排成一列，所以身高是參差不齊沒有排列過的。於是我先就把前面數來這第二個人把他從隊伍中叫出來叫他站在第一個人的旁邊，並且判定是否有沒有比第一個人矮，有的話就讓第一個往後退，第二個往前站在第一個人的位置。於是前面兩個已經暫時排序好了。

接下來我就叫第三個帥哥離開隊伍，叫他跟前面這第二個人做比較身高，如果這帥哥比較矮那麼這第二個人就往後退，接下來再次叫這帥哥跟第一個人比較一下身高，如果這帥哥又在次的比較矮那第一個人就往後退，帥哥這時就能夠順理成章的當第一個-目前最矮的傢伙。如果沒有那麼這個帥哥就排入原先第二個人的位置。(不要忘記這時候第二個人因為比這帥哥高，所以已經往後退退到帥哥原本的位置了，所以第二個位置就空起來了)

接下來的方式就是一模一樣，叫第四個跟前面那幾位來比較一下身高。第五個第六個亦然是如此。

如果你上面的說明有點看不懂或頭昏腦脹，我以下就每個句子就對應到程式碼來說明。

================================================================
首先我們把第二個人叫出來，於是你可以看到這個for loop是從這個隊伍的第二個人開始，然後在裡面持續的做身高的比較，直到最後的那個人也比較過：

   for (sofar = 1; sofar < size; ++sofar) {
   }

所以我們把這個帥哥從隊伍中叫出來：

     a_sofar = a[sofar];

把帥哥的身高記錄下來，這時候這個原本帥哥的位置就已經空掉了。之後他前面那個人如果比帥哥還高，那麼它就可以順理成章站在帥哥的這個位置，如果沒有，之後帥哥在乖乖的站回他原本的位置就行了。

接著我們開始把帥哥的身高和前面這幾位比較，首先我們比較他前面那一位：

      prev = sofar - 1;

並開始一個一個去比較，如果前面的一直比帥哥身高還高，就往後站，直到前面的某一位和帥哥身高一樣又或是比帥哥矮：

      while (prev >= 0 && a[prev] > a_sofar) {
         a[prev + 1] = a[prev];
         prev--;
      }

請注意這邊的比較迴圈有個先決條件就是前面的人不是幽靈(prev >= 0 )因為隊伍是從第0個開始排的，並沒有第-1個第-2個...所以我們設了這樣的條件，防止prev--會跑到幽靈人物那邊去。

最後這空的位置當然就給帥哥啦！

      a[prev+1] = a_sofar;

會跳出while比較迴圈並執行 a[prev+1] = a_sofar;只有三種情形：
 1. 一開始帥哥就比前面的還高，所以while不執行，直接執行 a[prev+1] = a_sofar;也就是帥哥被塞回去

2. 帥哥的身高中等，於是依他的身高前後都有人，那麼必然是因為while迴圈比較到一半發現他不符合a[prev] > a_sofar　因此執行了a[prev+1] = a_sofar;　所以prev這個人比帥哥矮或一樣，他沒有往後退，而prev+1這個位置原本的人因為比帥哥高，所以早就已經往後退了，因此這個prev+1的位置是空的，帥哥塞到這個位置是沒錯的。

3. 帥哥是最矮的，因此他是因為while迴圈發現了不符合prev >= 0(也就是prev = -1)了，所以該跳出迴圈去執行a[prev+1] = a_sofar; 那麼這時候a[prev+1] = a[0] 理所當然的帥哥應當順理成章的當目前最矮的傢伙。