前言

合併排序法顧名思義就是會有合併的動作，在合併之前想必應該會有切割的動作，一起來看看這這分分合合的演算法吧XD

生活常識

你有用切水果的經驗嗎？通常我們都習慣將一顆水果對半切，因為一整顆的水果比較不容易直皆整顆嗑，例如：西瓜XD，在對半切再對半切至小塊之後，就很容易不知不覺吃掉半顆，最後通通在肚子裡面集合了XD

圖片來源:https://www.pexels.com/zh-tw/photo/952480/

對半的這個概念，也很像有些店家的手工麵的製作過程，會看到師傅把麵團甩成麵條，過程中不斷的對折再對折，最後在剪斷就會變成可以下鍋煮的麵了

圖片來源:https://www.pexels.com/zh-tw/photo/3771814/

這樣一路分之後，會發生什麼事呢？就像三國演義裡面有這麼一句話：「天下大勢，分久必合，合久必分。」，其中的分久必合很有合併排序演算法的味道，分裂完之後，就會開始統一

圖片來源:https://www.books.com.tw/products/0010854705?sloc=main

團康遊戲中的「我是拳王」，就是在活動一開始，每一個人為一個單位，去找另一個人猜拳，如果猜輸，輸的人就要搭著猜贏者的肩膀成為他的隊友，如果猜贏，則可繼續找人猜拳，猜著猜著隊伍的人數會越來越多，最後剩下兩個隊伍時最刺激，因為猜贏者就是最大的勝利者，所有人都要排勝利者的後面，從此活動可以觀察出，從一開始一個人為單位，最後會合併成一大群人

專業知識 - 合併排序法 Merge Sort

合併演算法會將資料對切為兩個部分，然後再將左半邊與右半邊繼續再切一半，切到最小單位，也就是只剩下一個數值，已無法再被切割為止，然後再進行小單位之間整合，再到大單位之間的整合，最後將全部資料都排序好

分割

1. 取得資料長度，除以 2 之後， 將資料分為兩個區塊
   例如：有一陣列資料為：3, 8, 1, 7, 4, 2, 6, 5，共 8 個資料，除以 2 ，陣列會被分割為 2 個陣列 3, 8, 1, 7 與 4, 2, 6, 5，各自的長度為 4

2. 重覆第 1 個步驟，再將資料，除以 2 之後， 將資料分為兩個區塊
   例如：
   3, 8, 1, 7 會被分割為 2 個陣列，長度為 2 ：3, 8 與 1, 7
   4, 2, 6, 5 會被分割為 2 個陣列，長度為 2 ：4, 2 與 6, 5

3. 繼續重覆第 1 個步驟，直到陣列長度為 1 則可停止，表示已經完成分割動作
   例如：
   3, 8 會被分割為 2 個陣列，長度為 1 ：3 與 8
   1, 7 會被分割為 2 個陣列，長度為 1 ：1 與 7
   4, 2 會被分割為 2 個陣列，長度為 1 ：4 與 2
   6, 5 會被分割為 2 個陣列，長度為 1 ：6 與 5

合併

將目前最小單位的陣列兩兩合併，直到合併成一個大陣列為止

1. 選取兩個長度為 1 的陣列，取第一個值進行排序
   例如：
   3 與 8 ，由小到大排序之後，將兩個長度為 1 的陣列合併成長度為 2 的陣列：3, 8
   1 與 7 ，由小到大排序之後，將兩個長度為 1 的陣列合併成長度為 2 的陣列：1, 7
   4 與 2 ，由小到大排序之後，將兩個長度為 1 的陣列合併成長度為 2 的陣列：2, 4
   6 與 5 ，由小到大排序之後，將兩個長度為 1 的陣列合併成長度為 2 的陣列：5, 6

2. 選取兩個長度為 2 的陣列，取第一個值進行排序
   例如：
   3, 8 與 1, 7，由小到大排序之後，將兩個長度為 2 的陣列合併成長度為 4 的陣列： 1, 3, 7, 8
   2, 4 與 5, 6，由小到大排序之後，將兩個長度為 2 的陣列合併成長度為 4 的陣列： 2, 4, 5, 6
   

3. 選取兩個長度為 4 的陣列，取第一個值進行排序
   例如：
   1, 3, 7, 8 與 2, 4, 5, 6，將兩個長度為 4 的陣列合併成長度為 8 的陣列：1 ,2, 3, 4, 5, 6, 7, 8

分析

• 最壞的情況與最好的情況
  合併時需考慮此層級中有多少個數值，取最前面的數值互相比較之後才能決定排序，所以如果數值有 n 個，執行的時間就是 O(n)，另外因為不斷的對半切，會得到 log n 層，所以處理全部層級的時間為 O(n log n)

今日小結

合併排序法，就是分割至最小單位之後，兩兩比較排序並合併成較大的單位，再挑選兩個較大單位繼續兩兩比較，再排序並合併成更大的單位，直到最大單位出現即排序完成

今日謎題

演奏會持續進行，在中場休息時間，舉辦了一個有講徵答活動，題目裡面有一堆數字：4, 2, 3, 4, 5, 3, 4, 5，這些數字看起來似乎是一首歌的旋律，答案是等一下即將演奏的歌曲中某兩個小節，會由中西合併的樂手一起演奏，你能從推算過程中觀察出下一首要演奏的歌曲嗎？( 數字由小至大排列請將數字填入問號處，歌曲每小節有4拍，共四節，提示：5531　????　????　5353 )

昨日謎題

謎題說明：練習使用某一條件將資料分成兩堆，找出不具有對稱特質的字母被刪除，具有對稱特質的字母會被留下來，F、D、P、G、I、Q、J、V、I、D、R、Z、E，整理一下，就會得到 DIVIDE，就是快速排序採用的分而治之法(Divide-and-conquer)，你答對了嗎？