從IntroSort到MergeSort

Question

我知道當IntroSort被類似T []的東西調用時，比如Integer [] x;它會對數組進行排序，直到遞歸深度過多（在大多數實現中變爲0），然後它將切換到HeapSort。但是，當遞歸深度變爲2log2n時，我試圖調用修改後的MergeSort。修改後的MergeSort只使用原始數組大小一半的臨時數組，只是爲了節省一點時間和空間。無論如何，我基本上覆制了所有的QuickSort，除了在遞歸調用之前添加了depth_limit檢查。

private void quicksort(T[] items, int left, int right) { 
    int depth_limit = (int) (2*Math.log(items.length)); 
    if(depth_limit == 0) 
    { 
     mergesorter.sort(items, left, right); 
     return; 
    } 
    int pivotindex = findpivot(items, left, right); 

    // curr will be the final position of the pivot item. 
    int curr = partition(items, left, right, pivotindex); 

    if ((curr - left) > 1) { 
     quicksort(items, left, curr - 1); // Sort left partition 
    } 
    if ((right - curr) > 1) { 
     quicksort(items, curr + 1, right); // Sort right partition 
    } 
    } 

我認爲這會工作，因爲我相信

depth_limit = 2 *的log 2（n），其中n是輸入

所以我的問題是，我在哪裏檢查數量遞歸深度切換到MergeSort和我正確計算我的深度？

Answer 1

深度限制通常作爲一個參數傳遞，使用入口/幫助函數調用quicksort（）和深度限制的初始值。 Wiki有一個例子，排序（）是輔助函數經過深度限制到快速排序（）：

http://en.wikipedia.org/wiki/Introsort

items.length是不會改變。如果需要，使用（右 - 左）+1來獲取當前子數組的長度。

請注意，對於快速排序最糟糕的情況是，長度爲m的子數組被分成兩個子數組，其中一個長度爲1，長度爲m-1的一個，除非樞軸被排除，在這種情況下，最差遞歸的案例長度是1和m-2（該樞軸已經在適當的位置）。

合併排序只需要將從& T [左]到& T [右]的子數組排序。

自頂向下或自底向上合併排序可以通過對原始數組的兩半進行排序，然後將數組的前半部分複製到工作數組，然後使用1/2原始數組大小的工作數組將工作陣列和原始陣列的後半部分合併爲原始陣列（對於奇數尺寸原始陣列，工作陣列和「第一」半陣列尺寸爲n/2 + 1）。