# Algorithm_Sort_Insrtion sort
###### tags: `Algorithms` `Sort` `python`

def insertion_sort(input_array):
    """insertion sort
    input_array: list
                 list內的元素需為數值
                 
    return 
        由小大到排序後的list
    """
    if len(input_array) <= 1:
        return
    
    # 從第2個element開始處理
    for idx, idx_value in enumerate(input_array[1: ]):        
        # 內圈迴圈使用        
        inner_idx = idx        
        while inner_idx >= 0 and idx_value < input_array[inner_idx]:            
            # 這邊的idx剛好就是j-1的索引
            # 判斷兩值的大小，如果索引值(右)比前一個元素(左)小
            # 那就將前一個元素複製到索引處                                       
            input_array[inner_idx + 1] = input_array[inner_idx]                
            inner_idx -= 1            
        
        # 當兩個索引不同代表異動排序過
        if inner_idx != idx:                
            # 將原始索引值寫入最終停止的索引處            
            input_array[inner_idx + 1] = idx_value
    
    return input_array

下面給出五個資料集在不同資料量下的結果，其中
* l1: 已經排序好的，由小到大
* l2: 已經排序好的，但是逆排序，由大到小
* l3: 亂數生成
* l4: 亂數生成
* l5: 亂數生成

| Insertion sort | 20000 | 40000 | 60000 | 80000 | 100000 |
|---------------- |---------- |---------- |----------- |----------- |----------- |
| l1 | 7ms | 16ms | 25ms | 22ms | 37ms |
| l2 | 1min 31s | 5min 47s | 13min 27s | 24min 18s | 37min 34s |
| l3 | 43.4s | 2min 59s | 6min 52s | 12min 27s | 20min 6s |
| l4 | 43.1s | 3min 2s | 6min 50s | 13min 1s | 19min 52s |
| l5 | 42.9s | 2min 57s | 6min 51s | 12min 42s | 19min 47s |