Я работаю над проектом в своем классе структур данных. Проект заключается в реализации алгоритма сортировки слиянием с минимальным копированием. Идея состоит в том, чтобы выделить временное хранилище один раз, вне рекурсии, и избегать копирования до самого конца. Идея состоит в том, что каждый рекурсивный вызов сортировки слиянием «отбрасывает» данные между двумя массивами. Во-первых, мы рекурсивно сливаем сортировку от ввода к выводу. Затем мы объединяем вывод от вывода до ввода. Если мы отслеживаем, где находятся текущие данные (либо во входном массиве, либо в выходном массиве) во время рекурсии, тогда мы можем избежать копирования во время рекурсии и сохранять ее до самого конца.
Я знаю, как реализовать сортировку слиянием с использованием временного массивакак он используется для хранения промежуточных результатов. Здесь мы должны объединить сортировку в out, затем скопировать результаты рекурсивной сортировки обратно в in, а затем выполнить операцию объединения из in to out. Но моя проблема в том, чтоЯ не могу понять, как выполнить сортировку слиянием, вызвав temp один раз, а также избегая копирования до последнего.
Я уверен, что смогу закодировать программу, но мне нужно только лучшее понимание. Я нуждаюсь в некоторых глубоких объяснениях.