若 n 表示欲排序之記錄（Record）數量且 n＞2，下列為有關插入排序 （Insertion sort）演算法之敘述： <1>插入排序（Insertion sort）演算法之平均情況（Average case）、最佳情況（Best case）、最糟情況（Worst case）之時間複雜度皆相同。 <2>插入排序（Insertion sort）演算法具有“穩定（Stable）”性質。 <3>插入排序（Insertion sort）演算法是以比較鍵值為基礎之排序演算法，比較鍵值之次數與各記錄原始排列順序有關。 <4>插入排序（Insertion sort）演算法之最糟情況（Worst case）之時間複雜度發生於所有記錄已經依據 鍵值之順序排列時。 <5>使用插入排序（Insertion sort）演算法進行排序實際所需之時間與 n 值有關，但與記錄之長度無關。 請選出最適合之選項：
(A)<1><2>正確；<4><5>錯誤
(B)<3><4>正確；<1><5>錯誤
(C)<1><3>正確
(D)<4><5>錯誤

插入排序法(Insertion Sort)是排序演算法的一種，他是一種簡單容易理解的排序演算法，其概念是利用另一個數列來存放已排序部分，逐一取出未排序數列中元素，從已排序數列由後往前找到適當的位置插入。運算流程如下：

1. 從未排序數列取出一元素。
2. 由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。
3. 重複以上動作直到未排序數列全部處理完成。

流程示意圖：

然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地(In-place)的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。在與已排序的部分比較時，利用指派(Assign)的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。運算流程如下：

1. 將未排序的部分最左邊元素儲存到暫存變數。
2. 由後往前和已排序部分元素比較，若比自己大則將該元素往右邊位移。
3. 重複2的動作直到遇到不大於自己的元素，將暫存變數寫入在該元素之後；若都沒有則寫入在最前面。
4. 重複以上動作直到未排序部分全部處理完成。

流程示意圖：

分析

最佳時間複雜度：O(n)

平均時間複雜度：O(n^2)

最差時間複雜度：O(n^2)

空間複雜度：O(1)

Stable sort：是