歸並演算法的時間復雜度

① 歸並排序時間復雜度是什麼

歸並排序(MERGE-SORT)時間復雜度是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。

歸並演算法採用分治法，將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

其實現方式：先把待排序區間以中點二分；接著把左邊子區間排序；再把右邊子區間排序；最後把左區間和右區間用一次歸李廳並操作合並成有序的區間。

合並排序又稱為歸並排序演算法，是比較排序中時間復雜度最低巧磨的演算法（已經理論證明）。也孝擾斗是充分利用了分治思想，分而治之，將復雜重復的工作不斷進行分解至最小單元，而後逐層向上匯總，就像復雜的行政結構。