Переход от IntroSort к MergeSort

Question

Я знаю, что когда IntroSort вызывается с чем-то вроде T [], скажем Integer [] x; Он будет сортировать массив до тех пор, пока рекурсивная глубина не будет слишком большой (в большинстве реализаций будет 0), а затем переключится на HeapSort. Тем не менее, я пытаюсь вызвать модифицированный MergeSort, когда рекурсивная глубина становится 2log2n. Модифицированный 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 * log2 (п), где п число входов

Так что мой вопрос, где я могу проверить глубину рекурсии, чтобы переключиться на MergeSort, и я правильно вычислил свою глубину?

Answer 1

Ограничение глубины обычно передается как параметр, с функцией ввода/вспомогательной функции, которая вызывает quicksort() с начальным значением для ограничения глубины. Вики есть пример, сортировки() является вспомогательной функцией, которая проходит предел глубины для быстрой сортировки():

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

items.length не изменится. Используйте (справа налево) +1, чтобы получить длину текущего подматрица, если это необходимо.

Обратите внимание, что сценарий худшего сценария для быстрой сортировки состоит в том, что подматрица длины m делится на два подмассива, одна из длины 1, одна из длины m-1, если только стержень не исключен, и в этом случае длина регистров для рекурсии равна 1 и m-2 (стержень уже находится в правильном месте).

Сортировка слияния должна была бы отсортировать массив с & T [слева] до & T [справа].

Либо сортировка слияния сверху или снизу вверх может использовать рабочий массив 1/2 размера исходного массива, сортируя обе половины исходного массива, а затем копируя первую половину массива в рабочий массив, затем выполнение окончательного слияния рабочего массива и второй половины исходного массива обратно в исходный массив (для исходного массива нечетного размера рабочий массив и «первый» размер половинного массива составляют n/2 + 1).