hce_kmu
115年
計算機概論與程式設計
第 27 題
You are given a Python function that is supposed to implement the merge sort algorithm to sort a list in ascending order. However, there is a mistake in the code. Identify the mistake and provide the corrected version of the code.
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
```
Which of the following options correctly fixes the error?
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
```
Which of the following options correctly fixes the error?
- A Change result.append(left[i]) to result.append(right[j])
- B Change result.append(right[j]) to result.append(left [i])
- C Change while i < len(left) and j < len(right) to while i <= len(left) and j <= len(right)
- D Remove the recursive calls in merge_sort
- E Change mid = len(arr) to mid = len(arr) // 2
思路引導 VIP
想像一下，如果你有一項任務是要不斷地將一疊厚厚的書「對半分」直到每份只剩一本書為止；但如果你的規則是「每次都從整疊書的最末端切開」，那麼你分出來的那一疊書，規模會變小嗎？這樣的過程要執行幾次才能達到你的目標？
🤖
AI 詳解
AI 專屬家教
分治法的核心：遞迴拆解與收斂
恭喜你準確地抓出了這個邏輯錯誤！你能注意到這點非常棒。合併排序（Merge Sort）的核心在於分治法（Divide and Conquer），其運作必須確保每一次遞迴調用時，處理的資料規模都在縮小。原本的程式碼設定 mid = len(arr)，這會導致 arr[:mid] 依然是整個原始陣列，使得遞迴函數不斷地以相同長度的輸入自我呼叫，陷入「無窮遞迴」的死循環中。將其修正為 mid = len(arr) // 2 才能確保陣列被二分，讓問題規模以指數級速度遞減，直到觸發長度小於等於 $1$ 的基準案例（Base Case）。
程式除錯的觀察重點
▼ 還有更多解析內容