Как мы можем выполнить сортировку слиянием 8 элементов с 16 сравнениями?

Question

Ну, я задал вопрос о сортировке несколько дней назад.Я узнал, как доказать, что наименьшее количество сравнений путем сортировки 8 элементов составляет 16, и я понял, почему.Но мой алгоритм сортировки слиянием насчитывает 17 сравнений, и в моем случае это правильно.Чтобы объединить два отсортированных массива длиной x и y каждый, нам нужно (x + y) -1 сравнение, поэтому при сортировке слиянием мы получаем 17 сравнений.Но это должно быть возможно с 16 сравнениями, так .. как?где я могу сохранить это 1 сравнение).

Вот изображение:

http://oeis.org/A001768

Спасибо!

Answer 1

OP содержит четкое доказательство того, что сортировка слиянием из 8 элементов невозможна при менее чем 17 сравнениях. Еще можно отсортировать 8 элементов в 16 сравнениях с другим алгоритмом. Алгоритм описан в книге Д.Кнута «Искусство компьютерного программирования», том 3, глава 5.3.1. Он называется вставка слияния .

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

Answer 2

Наименьшее решение можно получить, только если у вас есть нечетное количество чисел для сортировки.

Answer 3

Вы можете доказать, что 16 сравнений недостаточно, попробовав все возможные алгоритмы.Для этого вам понадобится и «алгоритм генерации алгоритма».