Алгоритмы. Сортировка слиянием. Итерационный алгоритм. Реализация на Python и Java.

[@manOfPlanetEarth]

Смысл простой, но зашло очень тяжело: потому что эту тривиальность сложно положить в циклы. Пока проверил на листочке, что действительно нужны именно такие ограничения и именно такие приросты для переменных-бегунков, и именно такие границы при вызове merge() и именно прочувствовал механику алгоритма, ушло почти 2 дня... Ну и да, скачал cheatsheet Седжвика и Уэйна и смотрю, что у них mergesort относится к стабильной сортировке. В уроке нестабильный вариант, для стабильности надо добавить один символ:)) пс. автору благодарность за урок.

[@oleksandrtsymbaliuk]

Зато после этих сложностей можно прочувствовать красоту подхода. Так, что я надеюсь время было потрачено не зря.

[@manOfPlanetEarth]

@@oleksandrtsymbaliuk Да вообще любой алгоритм - это таинство результата от работы мысли других людей. Кто-то придумал и записал, вы изучили и сделали урок, а я просто изучаю всё готовое. Так что я иду про проторенной тропинке и не могу считать это самым сложным делом. Но иногда даже на проторенной тропинке приходится вспотеть.

[@radmitr]

Куда символ нужно добавить?

[@Kelbi28]

а для чего нам нужен вспомогательный массив, зачем мы делаем int[] supportArray=Array.copyOf...?

[@oleksandrtsymbaliuk]

Добрый день. Спасибо за проявленный интерес. Сам алгоритм слияния отсортированных подпоследовательностей подразумевает использования дополнительной последовательности. Вот именно ее роль и играет этот вспомогательный массив. Более подробно о слиянии вы можете узнать в этом видео - kzbin.info/www/bejne/iHvOn2R6jd57abc . Именно этот алгоритм слияния используется в этом алгоритме сортировки.

[@Kelbi28]

@@oleksandrtsymbaliuk Добрый день. И Вам спасибо за столь полезные уроки, с графическим объяснением, что делает пояснения более целостными. Я посмотрел данную ссылку и всю суть понял. для уточнения в техническом плане, я правильно понял, что под доп последовательностью у нас тут подразумеваются l и r?

[@oleksandrtsymbaliuk]

В лекции посвященной слиянию последовательностей (ссылку выше) в части посвященной слиянию отсортированной подпоследовательностей (конспект лекций начиная с 12 страницы) используются следующие обозначения: 1) l, r - индексы начала подпоследовательностей. Т.е. они указывают где расположены отсортированные подпоследовательности (части массива) в последовательности (массиве). В примере кода основной массив (array) дополнительный (supportArray) сначала копируем все содержимое основного массива в дополнительный, а потом уже сливаем в основной. 2) Под последовательностями в Java понимаем массивы. Основная это array, дополнительная supportArray.