歸并排序原理和步驟

1. 將數組分成兩半，直到每個子數組的長度為1

首先，將數組分成兩半。如果數組的長度大于1，將其從中間分割為兩個子數組。對每個子數組繼續進行這個過程，直到每個子數組的長度為1。此時，所有子數組都是有序的，因為單個元素的數組天然是有序的。

2. 遞歸地對每個子數組進行排序

在將數組分割為單個元素之后，通過遞歸方法對每個子數組進行排序。歸并排序的遞歸性質允許我們在底層子數組有序后逐層向上合并已排序的子數組。

3. 合并兩個已排序的子數組，得到一個已排序的數組

合并步驟是歸并排序的核心。對于兩個已經排序的子數組，通過比較它們的元素，將較小的元素依次放入新的數組中，直到所有元素都被處理完。這個過程會生成一個新的已排序數組。

4. 重復以上步驟，直到所有子數組合并成一個最終的排序數組

重復進行分割和合并的步驟，最終將所有子數組合并成一個整體，并且這個整體是有序的。通過這種遞歸分割和合并的方式，歸并排序能夠在 O(n log n) 的時間復雜度內完成對數組的排序。

歸并排序的完整步驟

1. 分割： 將數組分成兩個子數組。
2. 遞歸排序： 遞歸地對每個子數組進行歸并排序。
3. 合并： 合并兩個已排序的子數組，生成一個新的已排序數組。
4. 重復： 繼續對每個子數組進行分割、排序和合并，直到所有子數組合并成一個整體。

歸并排序的偽代碼如下：

void mergeSort(vector<int>& arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 遞歸排序左半部分mergeSort(arr, left, mid);// 遞歸排序右半部分mergeSort(arr, mid + 1, right);// 合并已排序的子數組merge(arr, left, mid, right);}
}void merge(vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;vector<int> leftArr(n1), rightArr(n2);for (int i = 0; i < n1; ++i)leftArr[i] = arr[left + i];for (int j = 0; j < n2; ++j)rightArr[j] = arr[mid + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];++i;} else {arr[k] = rightArr[j];++j;}++k;}while (i < n1) {arr[k] = leftArr[i];++i;++k;}while (j < n2) {arr[k] = rightArr[j];++j;++k;}
}

Python實現如下：

def merge_sort(arr):"""對數組進行歸并排序:param arr: 待排序的數組:return: 已排序的數組"""# 如果數組的長度為0或1，直接返回數組if len(arr) <= 1:return arr# 找到數組的中間點mid = len(arr) // 2# 遞歸地對左右兩個子數組進行排序left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])# 合并兩個已排序的子數組return merge(left, right)def merge(left, right):"""合并兩個已排序的子數組:param left: 左子數組:param right: 右子數組:return: 合并后的已排序數組"""result = []i = j = 0# 合并兩個子數組while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1# 追加剩余的元素result.extend(left[i:])result.extend(right[j:])return result