2S-1D против 2S-2D против многофазной сортировки файлов

Question

Может кто-нибудь объяснить мне, какие из них лучше, их сложность во времени и пространстве и что-нибудь важное, что, по вашему мнению, стоит знать. Я знаю, как работают 2S1D и 2S2D.

Answer 1

Я предполагаю, что "S" означает источник, а "D" означает место назначения, поэтому вы сравниваете 2 источника 1 назначения с 2 источниками 2 назначения и обычную сортировку слиянием с многофазной сортировкой слиянием. Статья вики включает в себя следующие случаи:

https://en.wikipedia.org/wiki/Polyphase_merge_sort

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

Для внутренней обычной сортировки слиянием с оперативной памятью для сортировки 2S-2D требуется только два массива, поскольку 2 источника могут быть четными, а нечетные - в одном массиве источников, а выходные данные также могут быть в одном массиве. Для внутренней многофазной сортировки слиянием необходимо как минимум 3 массива (2S-1D). В моей системе, даже если многофазная сортировка слиянием с 3 массивами делает на 5% больше ходов, чем обычная сортировка слиянием с 2 массивами, многофазная работа заканчивается примерно на 5% быстрее, возможно, из-за проблем с кешем.

Общая информация - для стека 3 (версия интерфейса 2S-1D только для LIFO) сортировка по многофазному слиянию выполняется быстрее всего.