歸并排序的時(shí)間復(fù)雜度：

1、歸并操作的工作原理包括申請(qǐng)空間使其大小為兩個(gè)已經(jīng) 排序序列之和，該空間用來(lái)存放合并后的序列，設(shè)定兩個(gè)指針最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置，比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間并移動(dòng)指針到下一位置，重復(fù)步驟3直到某一指針超出序列尾，將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

2、歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個(gè)非常典型的應(yīng)用，將已有序的子序列合并得到完全有序的序列，即先使每個(gè)子序列有序，再使子序列段間有序，若將兩個(gè)有序表合并成一個(gè)有序表稱為二路歸并。

3、按數(shù)量級(jí)遞增排列，常見(jiàn)的時(shí)間復(fù)雜度有常數(shù)階O(1)對(duì)數(shù)階O(log2n)，線性階O(n)，線性對(duì)數(shù)階O(nlog2n)，平方階O(n2)，立方階O(n3)，……k次方階O(nk)指數(shù)階O(2n)，隨著問(wèn)題規(guī)模n得不斷增大。

歸并排序和快速排序的區(qū)別：

1、先分解再合并：歸并排序先遞歸分解到最小粒度，然后從小粒度開(kāi)始合并排序，自下而上的合并排序;

2、邊分解邊排序：快速排序每次分解都實(shí)現(xiàn)整體上有序，即參照值左側(cè)的數(shù)都小于參照值，右側(cè)的大于參照值;是自上而下的排序;

3、歸并排序不是原地排序，因?yàn)閮蓚€(gè)有序數(shù)組的合并一定需要額外的空間協(xié)助才能合并;

4、快速排序是原地排序，原地排序指的是空間復(fù)雜度為O(1);

5、歸并排序每次將數(shù)組一分為二，快排每次將數(shù)組一分為三