Insertion Sorting 像是在玩 Poker，等到發牌的人發完牌的那刻，我們拿起手牌，通常都會把這堆無序的牌組重新排序，大多數人可能會從左至右、由小到大把牌整理好。

假設有五張牌，先不管花色，數字是 8, 4, 2, 13, 6，插入排序會把左一，也就是 8 當作起始點開始排序，跟下一張牌比大小，4 比 8 小，所以兩者要 "swap" 變成：

4, 8, 2, 13, 6

第二輪再往下一張牌去比，2 比 8 小，再次 swap 一次：

4, 2, 8, 13, 6

這時要把 current target 鎖定在 2 這個數字的位置，因為它要繼續跟前面的數字比看看，2 比 4 小所以要再 swap 一次：

2, 4, 8, 13, 6

然後才去 13 這邊，跟 8 比發現比它大就先不動，接著 6 比 13 小，所以 swap：

2, 4, 8, 6, 13

最後 6 再往前 swap 過來：

2, 4, 6, 8, 13

重點是在於 current target 要逐一跟前一個元素比對，不能像是我們實際玩牌那樣直接把牌插到正確位置，用程式碼實作的邏輯如下：

public static List<Integer> sortList(List<Integer> unsortedList) {
        for (int i = 0; i < unsortedList.size(); i++) {
            int current = i;
            while (current > 0 && unsortedList.get(current) < unsortedList.get(current - 1)) {
                int temp = unsortedList.get(current);
                unsortedList.set(current, unsortedList.get(current - 1));
                unsortedList.set(current - 1, temp);
                current--;
            }
        }
        return unsortedList;
    }

來看看這段邏輯具體的實作細節。

首先，能確定的是我們要迭代整個集合，要整理手牌當然是要把目光完整掃過每一張牌，不能漏掉某張，所以在這情況下從 0 開始用 for 迴圈迭代。

current 是為了每次排序到一個階段性的結果時，可以重新定位到要判斷的元素，因為不是每次互換後都可以直接往下做，我們還要考慮當前排序是否已經把最小的元素移動到最左邊了，如果還沒的話就要繼續比較，因此才有裡面的 while 迴圈，while 代表我們不確定要跑幾次，只要元素還能往前排就得繼續迭代。

current-- 是因為換完一輪後，小的那個元素已經往前移一格了，它要在那個位置繼續跟前一個元素比大小。

比完再回到大迴圈，大迴圈確保可以直接定位到下一個要判斷的地方。

最好的情況下時間複雜度是 O(n)，代表已排序，while 不會執行。
最壞就是 O(n)，巢狀迴圈。

空間都是 O(1)，in-place 記憶體佔用小。

資料量小適合（50筆上下吧），或是原先排序就沒有很亂的話。