Mergesort - снизу вверх быстрее, чем сверху вниз?

Ответ 1

Если быстрее вы имеете в виду меньше "итераций", тогда да. Если вам интересно, возможно, время выполнения.

Причина в том, что некоторые из этих 21 513 итераций делают больше, чем 22 527 итераций.

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

Ответ 2

Мне не удалось найти какое-либо обсуждение, в котором говорится, что один метод mergesort должен быть быстрее другого.

Сорта спуска и сверху вниз, а также другие варианты хорошо изучены в течение 90-х годов. В двух словах, если вы измеряете стоимость как количество сравнений отдельных ключей, лучшие затраты одинаковы (~ (n lg n)/2), наихудшая стоимость сверху вниз ниже или равна худшему случай снизу вверх (но и ~ n lg n), а средняя стоимость сверху вниз ниже или равна среднему случаю восходящего (но и ~ n lg n), где "lg n" - это двоичный логарифм. Различия связаны с линейными терминами. Конечно, если n = 2 ^ p, два варианта на самом деле точно совпадают. Это означает, что с точки зрения сравнения сверху вниз всегда лучше, чем снизу вверх. Кроме того, было доказано, что стратегия разделения "половинной половины" сортировки слияния сверху вниз является оптимальной. Исследовательские работы принадлежат Флайолету, Голину, Панни, Продингеру, Чену, Хвангу и Седжуику.

Вот что я придумал в своей книге "Дизайн и анализ чисто функциональных программ" (College Publications, UK), в Erlang:

tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T)           -> T.

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S,    T,      U) -> mrg(tms(S),tms(T)).

mrg(     [],    T)            -> T;
mrg(      S,   [])            -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg(  [X|S],    T)            -> [X|mrg(S,T)].

Обратите внимание, что это не стабильный вид. Кроме того, в Erlang (и OCaml) вам нужно использовать псевдонимы (ALIAS =...) в шаблонах, если вы хотите сохранить память. Трюк здесь состоит в том, чтобы найти середину списка, не зная его длины. Это делается cutr/3, который обрабатывает два указателя на входной список: один увеличивается на один, а другой на два, поэтому, когда второй достигает конца, первый находится посередине. (Я узнал об этом из статьи Оливье Данви.) Таким образом, вам не нужно отслеживать длину, и вы не дублируете ячейки второй половины списка, так что вам нужно только (1/2 ) n lg n дополнительное пространство по сравнению с n lg n. Это не очень хорошо известно.

Часто утверждается, что вариант снизу вверх предпочтительнее для функциональных языков или связанного списка (Knuth, Panny, Prodinger), но я не думаю, что это правда.

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

Кстати, существуют и другие варианты: сортировка слияния очереди и сортировка слияния в режиме on-line (я обсуждаю последнее в моей книге).

[EDIT: поскольку мерой стоимости является количество сравнений, нет никакой разницы между выбором массива и связанным списком. Конечно, если вы реализуете вариант с нисходящим списком со связанными списками, вы должны быть умны, так как вы не обязательно знаете количество ключей, но вам нужно пройти по меньшей мере половину ключей, каждый раз, и перераспределить, в общей сложности (1/2) n lg n клеток (если вы умны). Сортировка сложения снизу вверх со связанными списками на самом деле требует дополнительной дополнительной памяти, n lg n + n ячеек. Таким образом, даже со связанными списками вариант сверху вниз - лучший выбор. Что касается длины программы, ваш пробег может отличаться, но на функциональном языке сортировка слияния сверху вниз может быть короче, чем снизу вверх, если стабильность не требуется. Существуют некоторые документы, в которых обсуждаются вопросы реализации слияния, например, на месте (для которых вам нужны массивы) или стабильности и т.д. Например, "Тщательный анализ программ Mergesort", Katajainen и Larsson Traff (1997).]

Ответ 3

Я задал тот же вопрос на форумах классов coursera для августовского издания этого курса. Профессор Кевин Wayne (из Принстона) ответил, что во многих случаях рекурсия быстрее, чем итерация из-за кеширования улучшенных характеристик.

Итак, короткий ответ, который я получил в то время, заключался в том, что сортировка слияния сверху вниз будет быстрее, чем сортировка слияния снизу вверх из-за причин кэширования.

Обратите внимание, что класс преподавался на языке программирования Java (не Javascript).