4. 依據圖一中的程式作答。圖中 Python function 的功能是實現哪一種排序（sorting） 技術？
(A) 氣泡排序（bubble sort）
(B) 選擇排序（selection sort）
(C) 插入排序（insertion sort）
(D) 快速排序（quick sort） 新 聞 稿 專 用 第 2 頁，共 8 頁

該 Python 函式 sort(arr) 的功能是實現一種排序技術。讓我們逐步分析這段程式碼：

1. def sort(arr): 定義了一個名為 sort 的函式，接受一個列表 arr 作為輸入。
2. n = len(arr) 獲取列表的長度。
3. if n <= 1: return arr 處理基本情況：如果列表長度為 0 或 1，則已排序，直接返回。
4. for i in range(1, n): 外層迴圈從列表的第二個元素（索引為 1）開始遍歷到最後一個元素。
5. key = arr[i] 將當前要插入的元素儲存到 key 變數中。
6. j = i - 1 設定一個指針 j，指向 key 前面已排序部分的最後一個元素。
7. while j >= 0 and key < arr[j]: 內層 while 迴圈是關鍵的移動步驟。它會將已排序部分中比 key 大的元素向右移動一個位置，為 key 騰出空間。
   • arr[j + 1] = arr[j] 將 arr[j]（已排序部分的元素）向右移動一位。
   • j -= 1 將指針 j 向左移動，繼續與前一個元素比較。
8. arr[j + 1] = key 當 while 迴圈結束時（找到 key 的正確位置，或 j 超出範圍），將 key 插入到騰出的位置。
9. return arr 返回排序後的列表。

這個邏輯與**插入排序（Insertion Sort）**演算法完全一致。插入排序的工作原理是將未排序的元素逐一插入到已排序部分的正確位置。

因此，圖中 Python 函式實現的是插入排序技術。