У меня возникли проблемы с преобразованием рекурсивной сортировки слияния в сортировку слияния на основе стека. Наличие двойных рекурсивных вызовов в функции отбрасывает меня. Я не уверен, как я должен подходить к этому.Слияние на основе стека Сортировка C
Вы можете реализовать mergesort итерационно, объединяя смежные срезы из 2^k элементов, от k = 0 до 2^k> = n. Это довольно просто, нет необходимости в преобразовании стека рекурсивного алгоритма.
Для этого вам потребуется дополнительное пространство, как правило, такого же размера, как и набор данных. Вы можете выделить это пространство malloc или использовать автоматическое хранилище, если оно не слишком велико (распределение на основе стека). Но это требование памяти аналогично требованию рекурсивной реализации.
Слияние ломтиков элементов 2^k немного менее эффективно, если общее количество элементов не равно 2, и оно выполняет больше сравнений и использует вдвое больше памяти, но общая сложность по-прежнему равна O (n * log (n)) в худшем случае, и умная реализация может привести ее к O (n) для отсортированного случая.
Попробуйте этот подход, я выложу код после того, как вы покажете свои собственные попытки.
@ panw1: Не пытайтесь? Вы отказались от этой проблемы? – chqrlie
Оба верхних (рекурсивных) и снизу вверх требуют дополнительного пространства. Учитывая второй массив темпа того же размера, что и исходный массив, сортировка как сверху вниз, так и снизу вверх работает с индексами (в отличие от альтернативного метода сверху вниз, который многократно выделяет и освобождает частичные массивы). – rcgldr