Почему четное-нечетное разделение «быстрее» для MergeSort?

Question

MergeSort - это алгоритм «разделяй и властвуй», который делит входные данные на несколько частей и рекурсивно решает части.

... Существует несколько подходов для функции разделения. Один из способов - разделить середину. У этого подхода есть несколько приятных свойств, однако мы сосредоточимся на методе, который немного быстрее: четно-нечетное разбиение. Идея состоит в том, чтобы поместить каждый элемент четной позиции в один список, а каждую нечетную позицию - в другой.

Это прямо из моих лекционных заметок. Почему именно четное-нечетное разбиение происходит быстрее, чем в середине массива?

Я предполагаю, что это как-то связано со списком, который передается в MergeSort и имеет качество уже отсортированного, но я не совсем уверен.

Может ли кто-нибудь пролить свет на это?

Редактировать: я пытался запустить следующее в Python ...

global K
K = []
for i in range (1, 100000):
    K.append(i)


def testMergeSort():
"""
testMergeSort shows the proper functionality for the
Merge Sort Algorithm implemented above.
"""

t = Timer("mergeSort([K])", "from __main__ import *")
print(t.timeit(1000000))

p = Timer("mergeSort2([K])", "from __main__ import *")
print(p.timeit(1000000))

(MergeSort - это четно-нечетная MergeSort, MergeSort2 делится по центру)

И результат был:

0,771506746608

0,843161219237

Answer 1

Чем ближе входной список к уже отсортированной, тем меньше время выполнения (это потому, что процедуре merge не нужно move любое из значений, если все уже в правильном порядке; выполняет O ( n ) сравнений.Так как MergeSort рекурсивно вызывает себя на каждой половине разбиения, нужно выбрать функцию split, которая увеличивает вероятность того, что результирующие половины список в отсортированном порядке. Если список в основном отсортирован, то разделение по четному-нечетному будет лучше, чем разделение по середине. Например,

MergeSort([2, 1, 4, 3, 5, 7])

приведет к

Merge(MergeSort([2, 1, 4]), MergeSort([3, 5, 7]))

если мы разделим середину (обратите внимание, что в обоих подсписках есть ошибки сортировки), тогда как если бы мы делали четно-нечетное разделение, мы получили бы

Merge(MergeSort([2, 4, 5]), MergeSort([1, 3, 7]))

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

Answer 2

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

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

Я должен добавить, что я не специалист по этим вопросам, они просто приходят на ум ...

Answer 3

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

Несмотря на это, здесь есть чат об этом: https://cstheory.stackexchange.com/questions/6732/why-is-an-even-odd-split-faster-for-mergesort/6764#6764 (и да, я действительно опубликовал подобный ответ там (полное раскрытие))

В соответствующих статьях Википедии указывается, что сортировка слиянием равна O (n log (n)), а сортировка нечетно-четного слияния равна O (n log (n) ^ 2). Odd-Even, конечно, «медленнее», но сеть сортировки статична, поэтому вы всегда знаете, какие операции вы собираетесь выполнять и (глядя на графику в записи в Википедии), заметьте, как алгоритм остается параллельным, пока конец.

Где, когда сортировка слиянием, наконец, объединяет 2 списка, последние сравнения 8-элементной сортировочной сети для сортировки слиянием нечетных и четных остаются независимыми.