Сортировка слиянием. Является ли сортировка снизу вверх быстрее, чем сортировка сверху вниз?

. Я читал "Алгоритмы, 4-е изд." Седжвика и Уэйна и параллельно реализовывал алгоритмы, обсуждаемые в JavaScript.

Недавно я использовал примеры сортировки слиянием, представленные в книге, чтобы сравнить подходы «сверху вниз» и «снизу вверх»… но я обнаружил, что восходящий метод работает быстрее (я так думаю). Смотрите мой анализ в моем блоге. - http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/

Мне не удалось найти обсуждения, в котором говорится об одном методе сортировки слиянием должен быть быстрее, чем другой. Является ли моя реализация (или анализ) ошибочной?

Примечание: мой анализ измеряет итерационные циклы алгоритма, а не строго сравнивает/перемещает массив. Может быть, это неправильно или неактуально?

РЕДАКТИРОВАТЬ: В моем анализе не учитывалась скорость, поэтому мое утверждение о том, что она работает «быстрее», немного вводит в заблуждение. Я отслеживаю «итерации» с помощью рекурсивного метода (сверху вниз) и циклов for (снизу вверх) — и кажется, что снизу вверх используется меньше итераций.

13
задан jayelm 20 February 2014 в 19:35
поделиться