Merge Sort概述

分而治之算法

遞歸地將問題分解為多個子問題，直到它們變得簡單易解
將解決方案組合起來，解決原有問題

O（n*log（n））運行時間

基于比較的算法的最佳運行時間

一般原則
·合并排序:
1. 將數組分成兩半
2.在每一半上調用合并排序以遞歸排序
3.將兩個已排序的兩半合并為一個已排序數組

看一個例子：

2，6，5，1，7，4，3

首先第一步，是將數組分成兩半，分到直到分不了了。

然后現在，對每組數據進行排序。

2，6

1，5

4，7

然后，再一組一組排序：
1，2，5，6

3，4，7

然后最后兩組排序

1，2，3，4，5，6，7

注意這里是，1和3比，選1，2和3比，選2，5和3比，選3，4和5比，選4。。。

Python實現MergeSort合并排序

def merge_sort(arr):if len(arr) > 1: #要保證大于1才能排序left_arr = arr[:len(arr)//2] #定義2個子數組，這個是從索引0到中心點，：左留下空白就是取左邊所有right_arr = arr[len(arr)//2:] #這個是從中心點到右邊# 遞歸merge_sort(left_arr)merge_sort(right_arr) #分別再左右兩個數組進行遞歸# 執行以上兩行以后，左右兩個數組都按照順序排列了# 合并# 現在兩個數組已經拍好順序，我們想讓兩個數組，第一個數組的最左邊和第二個數組最左邊進行比較# 所以，創建索引進行追蹤i = 0 #追蹤第一個左邊數組j = 0 #追蹤右邊k = 0 #追蹤合并數組中的索引while i < len(left_arr) and j < len(right_arr):if left_arr[i] < right_arr[j]:#如果左邊的數組值小arr[k] = left_arr[i] # 保存索引對應的值i += 1#k += 1#因為我們取得是i的值，所以，必須i+1進入下一個索引，而且，k是合并后的數組，也要進入下一個else:arr[k] = right_arr[j]j += 1#k += 1k += 1  #簡略后，放這里# 現在只考慮轉移左邊的數組，不考慮右邊的數組;# 這是假設，右邊都排好了，但是左邊沒排完while i < len(left_arr):arr[k] = left_arr[i]i += 1k += 1# 假設左邊都排好了，但是右邊還要排while j < len(right_arr):arr[k] = right_arr[j]j += 1k += 1arr_test = [2,3,5,1,7,4,4,4,2,6,0]
merge_sort(arr_test)
print(arr_test)

問題：
?

 merge_sort(left_arr)
2    merge_sort(right_arr) #分別再左右兩個數組進行遞歸
3    # 執行以上兩行以后，左右兩個數組都按照順序排列了    這里是什么意思？是直接調用我定義的函數嗎？函數不是沒寫完嗎？

這里正是體現了遞歸函數的工作原理。當你在代碼中調用 merge_sort(left_arr) 和 merge_sort(right_arr) 時，你實際上是在調用當前函數自身，但是傳入了不同的參數——即左側子數組和右側子數組。

雖然從直觀上看，函數“還沒有寫完”，但實際上，每次調用 merge_sort 函數時，它都在執行完整的邏輯流程：

1. 檢查當前數組的長度是否大于1，如果是，則繼續執行。
2. 將當前數組分割成兩個子數組（左側和右側）。
3. 對這兩個子數組分別遞歸調用?merge_sort?函數。這里就是遞歸發生的地方，每一次這樣的調用都會重復整個過程，直到數組被拆分到不能再拆分（即長度為1或0，視為已排序）。
4. 最后，通過合并這些小數組來完成排序。

因此，即便在某次調用中函數尚未執行到合并步驟，之前的調用（處理更小規模數組的那些調用）已經在逐步完成它們的任務。當這些更深層次的遞歸調用返回時，它們會逐級返回到上一層，最終回到最初的函數調用，這時所有子數組都已經排序完畢，可以進行最終的合并，完成整個數組的排序。