在本文中，我們將討論合并排序算法。我們將看到一些可視化示例來幫助理解算法，然后使用Java和Python代碼實現它。

　　什么是合并排序算法？

　　合并排序算法是基于分而治之算法的高效排序算法。它將元素的集合(數組)劃分為單個單元，然后以有序的方式合并它們。

　　讓我們看一個示例來了解合并排序的工作原理。

　　我們將使用合并排序算法對以下數字數組進行排序：4， 10， 6， 14， 2， 1， 8， 5

　　下圖顯示了“劃分”過程：

　　該數組首先分為兩個單獨的數組。然后這些陣列也被分割。這種劃分一直持續到陣列中的所有元素都成為一個單元。

　　在此階段之后，合并開始。這是如何發生的：

　　這些元素正在重新分組到數組中，但這次是按排序順序排列的。就像它們被拆分一樣，它們正在被合并。

　　在我們使用代碼實現此算法之前，您應該了解我們如何能夠按排序順序收集這些元素。

　　我們將使用將元素重新組合成兩個單獨數組的部分 - 4，6，10，14和1，2，5，8。下面是一個插圖，用于了解我們是如何到達最終數組的：

　　如上所示，我們有兩個箭頭指向兩個數組的第一個索引。將進行比較以找出哪個索引較小。在我們的例子中，1小于4，因此將被推送到合并的數組。然后，紅色箭頭將移動到下一個索引。那是：

　　將進行另一個比較：2<4?

　　2 小于 4，因此它將被推送到合并的數組，箭頭移動到下一個索引。

　　對于下一個比較：

　　4 小于 5，因此 4 將被推送到合并的數組，青色箭頭將移動到下一個索引。

　　這種比較將一直持續到合并的數組被填滿。如果它到達一個數組變為空的點，則具有剩余元素的數組將按排序順序復制到合并的數組中。

　　讓我們看一些代碼示例！

　　Java 中的合并排序示例

　　如果我們想用Java實現合并排序，那會是什么樣子：

　　讓我們分解代碼。

　　在上面，我們創建了數字數組。之后，我們調用該方法對數字進行排序。然后，我們循環遍歷排序后的數字數組，并將它們打印到控制臺。mergeSort

　　我們通過將數組長度除以二來獲得數組的中點。左數組從第一個索引開始到中點，而右數組從中點之后的索引開始到數組結束的位置。

　　然后，我們創建了兩個循環，根據元素的位置將元素復制到左側和右側數組中。然后，我們在左側和右側數組中調用該方法。這將以遞歸方式分解數組，直到數組被縮減為單個單元(就像我們在上一節中的圖像中看到的那樣)。mergeSort

　　最后，我們調用該方法以按排序順序將數組合并為一個數組。讓我們看一下該方法中使用的邏輯。merge merge

　　還記得上一節中圖像中的箭頭嗎?我們在這里使用然后用于合并數組來表示它們，其中數字將按排序順序推入其中。xyz

　　while 循環用于在兩個數組上進行比較并更改 的位置，并且當元素被推入合并數組時。xyz

　　Python 中的插入排序示例

　　此處的邏輯與上一節中的邏輯完全相同。上面，我們使用Python實現了合并排序算法。您可以在上一節中找到有關代碼工作原理的說明。

　　合并排序的時間復雜度是 O(n*Log n)適用于所有情況(最佳、平均和最差)。

　　結論

　　在本文中，我們了解了合并排序算法的工作原理。然后，我們看到了一些示例以及如何在 Java 和 Python 代碼中應用它。