Почему у mergesort есть не более 6 n log n массивов?

Question

Я наблюдаю за лекцией алгоритмов Coursera Princeton по сортировке слияния, и я понимаю весь анализ, за ​​исключением того, что слияние происходит не более чем на 6 n log n доступа к массиву.

Почему 6?

Answer 1

Чтобы получить 6 массива имеет доступ, несколько неэффективный процесс слияния:

read - read an element from even run for compare 
read - read an element from odd run for compare 
     - compare 
read - read the lower element again for copy 
write - write the lower element to the output array for copy 
... - after merge copy back 
read - read element from output array to copy back 
write - write element back to original array to copy back 

Нормальный случай один для чтения и один записи для каждого элемента перемещается, но рассмотрим случай, когда элементы являются слишком большими, чтобы поместиться в переменная, как строка, поэтому после сравнения строка, которую нужно переместить, должна быть прочитана снова.

Обычно операции копирования можно избежать, в зависимости от того, как кодируется сортировка слияния.

Answer 2

Я также задавался вопросом о 6. Я смотрел анализ Тима Рагхардена (видеоролик «1-7» - «Сортировка сортировки» (9 мин) .mp4 »), и он также говорит шесть. Каждое объяснение чувствует себя рукой машет, но, может быть, потому что это так просто они не понимали, что нужно объяснение:

Вы получаете доступ массив дважды для каждого п (или к) при копировании на вспомогательный массив aux[k] = a[k]; Тогда, в худшем случае вы никогда не исчерпываете суб-массив (где вы только сравниваете константы), так что у вас есть еще четыре доступа к массиву else if (less(aux[j], aux[i])) a[k] = aux[j++]; (например, если вход находится в обратном порядке) или каждый сбой сравнивается, а остальные удары в после сравнения (правильный порядок) или некоторой комбинации двух. Это не имеет значения, просто по определению наихудшего случая вы не можете избежать доступа к массиву через константы (с if (i > mid) или else (j > hi)), так что у вас есть еще четыре для каждого k. Тоталь 6.

(Каждая строка кода Седжвика. - страница P271 его текста)