Сортировку слиянием можно выполнить на месте для списка, в отличие от массива.
Однако я еще не нашел ссылки, объясняющей, как это достигается.
Любой указатель приветствуется.
Использование сортировки слиянием для списка
comment
На этот вопрос есть несколько хороших ответов: stackoverflow.com/q/2571049
- person blgt   schedule 19.06.2014
comment
Вы имели в виду связанный список? (массив также является списком)
- person wildplasser   schedule 20.06.2014
comment
возможный дубликат сортировки слиянием связанного списка
- person Jim Mischel   schedule 20.06.2014
comment
Вы проводили какое-нибудь исследование? Ввод связанного списка сортировки слиянием в Google дал много хороших примеров.
- person Jim Mischel   schedule 20.06.2014
Ответы (1)
На самом деле возможно, хотя и непросто, реализовать сортировку слиянием на месте для массивов. Со связанными списками проблема становится довольно простой. Каждый узел в связанном списке просто имеет значение и указатель на следующий узел. Разбить связанный список пополам довольно просто. Просто перейдите к среднему узлу, возьмите его преемника в качестве главы вашего второго списка, а затем установите для преемника значение null.
Шаг слияния работает так, как и следовало ожидать. Не создавайте никаких новых узлов, просто повторно свяжите узлы из двух ваших списков.
person
Wcrousse
schedule
20.06.2014