Insertion sort

• 原理
  • index 从 1 开始
  • 暂存第 j 个，i = j - 1, i 不停往上覆盖
• Invariant: Sorted in 0-1

void insertSort(int array[], int length)
{
    for (int j = 1; j < length; j++)
    {
        int key = array[j];
        int i = j - 1;
        while (i >= 0 && array[i] > key)
        {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = key;
    }
}