IntroSortからMergeSortへ行く

Question

IntroSortがT []のようなもので呼び出されたとき、Integer [] x;再帰深度が大きすぎる（ほとんどの実装では0になる）まで配列をソートし、次にHeapSortに切り替えます。しかし、再帰深度が2log2nになったときに、変更されたMergeSortを呼び出そうとしています。修正されたMergeSortは、わずかな時間とスペースを節約するために、元の配列のサイズの半分の一時配列しか使用しません。とにかく、基本的には、再帰的に呼び出す前にdepth_limitチェックを追加した以外は、QuickSortのすべてをコピーしました。

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 * LOG2（n）は、nは入力

の数であるので、私の質問があり、信じているので、私は、これが働くだろうと思うだろうMergeSortに切り替えるための再帰の深さと深さを正しく計算していますか？

Answer 1

深度制限は通常、深度制限の初期値でquicksort（）を呼び出すエントリ/ヘルパ関数を使用してパラメータとして渡されます。ウィキ例を有し、ソート（））クイックの深さの制限を（通過ヘルパー関数である：

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

items.lengthは変更するつもりはありません。これが必要な場合は、現在のサブ配列の長さを取得するために（右 - 左）+1を使用します。

クイックソートの最悪のシナリオは、ピボットが除外されない限り、長さmのサブ配列が長さ1、長さm-1の2つのサブ配列に分割されていることです。再帰のケース長は1とm-2です（ピボットはすでに適切な場所にあります）。

マージソートでは、サブ配列を& T [左]から& T [右]にソートするだけで済みます。

トップダウンまたはボトムアップマージソートでは、元の配列の2つの半分をソートして、作業配列に最初の半分をコピーしてから元の配列のサイズの1/2を使用することができます。作業配列と元の配列の後半を元の配列に最終的にマージします（奇数サイズの元の配列の場合、作業配列と "最初の"半分の配列サイズはn/2 + 1です）。