申論題

歸併排序（Merge Sort）是一種高效的、基於比較的、分而治之的排序演算法。它的基本思想是將一個大數組分成兩個較小的數組去解決，然後遞歸地對這兩個小數組應用歸併排序，最後將排序好的兩個小數組合並成一個大的有序數組。
歸併排序的步驟：
.分割：將當前數組分成兩個大小大致相等的子數組，直到每個子數組只有一個元素或為空，因為單個元素自然是有序的。
.征服：遞歸地對兩個子數組應用歸併排序，直到子數組完全有序。
.合併：將兩個有序的子數組合並成一個有序的數組。
特性：
穩定性：歸併排序是一種穩定的排序演算法，即相等的元素之間的相對順序在排序後不會改變。
非就地排序：在合併過程中需要額外的存儲空間來暫存數組，因此歸併排序不是就地排序演算法。
時間複雜度：歸併排序的時間複雜度為O(nlogn)，其中n是數組的長度。這個時間複雜度在最壞、平均和最好情況下都保持不變。
空間複雜度：由於需要額外的數組來合併兩個子數組，歸併排序的空間複雜度為O(n)。