Please enable JavaScript.

Coggle requires JavaScript to display documents.

Merge Sort(合併排序) - Coggle Diagram

- - - - 分割：遞迴地把當前序列平均分割成兩半，直到每個陣列中只剩 1 元素
        
        n-1 個步驟
        
        O(n)
      - 整合：在保持元素順序的同時將上一步得到的子序列整合到一起（合併）
        
        每回合的合併需要花：O(n)
        
        O(n log(n))
        
        總共需要回合數：O(log n)
    - - 遞迴法（Top-down）
        
        示意圖
      - 疊代法（Bottom-up）
        
        原理如下（假設序列共有 n 個元素）：
        
        互相比較序列內相鄰 2 數字之大小，並排序(此時，1 or 2 數字一組)
        
        排序 2 組 2 數字的序列(此時，3 or 4 數字一組)
        
        重複步驟2，直到所有元素排序完畢