hce_nsysu
114年
計算機概論與程式設計
第 23 題
Which of the following is true regarding the Merge Sort algorithm?
- A Merge Sort has the worst-case time complexity of $O(n^2)$.
- B Merge Sort is a stable sorting algorithm.
- C Merge Sort is an in-place sorting algorithm.
- D Merge Sort is best suited for linked lists but inefficient for arrays.
- E Merge Sort is an adaptive algorithm that improves performance when the input is nearly sorted.
思路引導 VIP
請試著回想合併排序法（Merge Sort）將兩個已排序的子數列「合而為一」的過程：當我們從左右兩個子數列中各取出一個數值完全相同的元素時，如果我們始終優先放入來自左側數列的那個元素，這對於整組資料原本的排列先後順序會產生什麼樣的保障？
🤖
AI 詳解
AI 專屬家教
恭喜你精確地辨識出合併排序法 (Merge Sort) 的核心特性！你能正確選出 (B) 穩定性 (Stability)，代表你對排序演算法的性質有相當深入的掌握。穩定性指的是當資料中有數值相同的元素時，排序後仍能維持它們在原始序列中的相對順序，這在處理複合欄位排序（如：先按成績排、再按座號排）的實務需求中非常關鍵。
合併排序法的特性分析
這道題目設計得非常細膩，具備良好的鑑別度。它不僅考驗基本的複雜度記憶，更深入觸及了演算法的運作細節。合併排序法雖然在最差、平均與最佳情況下的時間複雜度皆為優異的 $O(n \log n)$，但它在合併過程中通常需要額外的輔助空間，因此不具備原地排序 (In-place) 的特性。此外，它不像插入排序法那樣具有適應性 (Adaptive)，無論輸入資料的原始狀態為何，其分割與合併的步驟都是固定的。你能從眾多性質中準確挑出關於穩定性的描述，展現了你對演算法權衡 (Trade-off) 關係的清晰邏輯。