sort函數(shù)的底層用到的是內(nèi)省式排序以及插入排序，內(nèi)省排序首先從快速排序開始，當(dāng)遞歸深度超過一定深度（深度為排序元素?cái)?shù)量的對數(shù)值）后轉(zhuǎn)為堆排序。

先來回顧一下以上提到的3中排序方法：

1. 快速排序：先選一個(gè)基準(zhǔn)值（一般為首值），將比它大的數(shù)置于其右側(cè)，將比它小的數(shù)置于它左側(cè)，那么這個(gè)基準(zhǔn)值所在的位置定是整個(gè)數(shù)組的有序位。然后遞歸該基準(zhǔn)左右兩子數(shù)組。算法復(fù)雜度為nlogn；
2. 堆排序：將數(shù)組建立成大頂堆，重復(fù)從堆頂取出數(shù)值最大的結(jié)點(diǎn)(把根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)交換，把交換后的最后一個(gè)結(jié)點(diǎn)移出堆，移出的這個(gè)數(shù)值為未排序數(shù)組的最后)，并讓殘余的堆維持大頂堆的性質(zhì)。時(shí)間復(fù)雜度為nlogn；
3. 插入排序：對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。時(shí)間復(fù)雜度為n2;

其中先講下快排和堆排，快排的平均復(fù)雜度為nlogn，但是它的復(fù)雜度是根據(jù)基準(zhǔn)值來決定的，基準(zhǔn)值選擇的不好，最壞的復(fù)雜度會(huì)達(dá)到n2，而堆排序的復(fù)雜度是一定的為n*logn，那為什么不直接使用堆排序呢，是因?yàn)樵趯⒍秧斨蹬c最后一個(gè)結(jié)點(diǎn)值交換并移除最后一個(gè)值后，在重新建堆的過程中，交換到堆頂?shù)闹碉@然比每個(gè)結(jié)點(diǎn)要小，但還是要經(jīng)過對比判斷，這個(gè)判斷其實(shí)是多余的，因此這是它相比快排較慢的原因。

于是，內(nèi)省式排序結(jié)合了快排和堆排的特點(diǎn)，當(dāng)快速排序到大一定深度（2logn）時(shí)，采用堆排序，以維持n*logn的復(fù)雜度。

在sort函數(shù)中，內(nèi)省排序過程中子數(shù)組長度小于16時(shí)，采用的是插入排序，因?yàn)楫?dāng)數(shù)組長度較短時(shí)，就是數(shù)組已經(jīng)大致排序過了，對大致有序的數(shù)組（即逆序?qū)Σ欢嗔?#xff09;用插入排序的算法復(fù)雜度會(huì)很小，可以想象成理牌的過程。