Comments 21
Кажется, это статья из цикла "сейчас я буду объяснять алгоритм, пока не пойму его".
ЗЫ: Выделяет, кажется, в общей сложности 2N (для вложенных уровней рекурсии массивы короче). Непривычно, обычно сортировки делают in-place (если это не махровая функциональщина)
Да не, O(N). Прикиньте момент, когда рекурсия дошла до дна: на самом верхнем уровне (сортируем массив длиной N) выделено два массива по N/2, уровнем ниже (сортируем массив длиной N/2) два по N/4 и так далее. В сумме 2N.
Тут больше доставляет, что будет проделано O(N) выделений из кучи. Сама сортировка, мне кажется, за этим потеряется.
уровнем ниже (сортируем массив длиной N/2) два по N/4 и так далеено уровнем ниже нам нужно отсортировать ДВА массива по N/2, то есть выделяем 4 по N/4. Разве нет?
Спасибо за замечание. Полностью согласен с тем, что с точки зрения использования памяти данное решение неэффективно.
А зачем тут вообще память то выделять?
Меняем объекты списка сначала в парах, потом в четверках, и. т д. И лучше в цикле, а не рекурсией, ибо рекурсия и стек жрет, и время на вызовы-возвраты.
Если хочется ускорить процесс, то создаем буфер и индексами, или указателями на обьекты и сортируем его. Тогда экономим время на многократном свапе объектов.
В парах можно. А вот в четвёрках и дальше у вас поменять уже без дополнительной памяти не получится. Там может оказаться надо переместить 2/3 правого массива в начало, а левый и оставшуюся 1/3 правого склеить вперемешку. Тогда непонятно, куда деть первые 2/3 левого массива так, чтобы это было быстро, не рушило порядок элементов в нём, и элементы можно было отличить от оставшихся элементов правого массива.
In-place сортировка слиянием — на удивление сложная штука.
Иногда доступна ТОЛЬКО РЕКУРСИЯ, в функциональных языках, к примеру. Выполняя сортировку в цикле сложно будет её распараллелить в случае огромных объёмов, а совершая сортировку рекурсией, в принципе это не сложно. Все эти кажущиеся странные алгоритмы предназначены для функционального программирования, а там своя специфика и свои преимущества. Несмотря на избыточность по потреблению памяти, алгоритм этот будет гораздо легче распараллелить или сделать его на каком-то поточном процессоре будущего, который одновременно может исполнять разные стадии сортировки, в отличие от типичного процессора, который в каждый момент времени работает только с одним элементом. И тут становится актуальным именно копирование данных, хоть оно и приводит к дублированию, но зачастую копирование без возможности последующей модификации(возврат значения в те же ячейки) очень ускоряет работу кеша процессора(нет необходимости синхронизировать кеш между ядрами, выгружать кеш-линию обратно в RAM и т.д.), в итоге растёт производительность в целом и очень значительно.
Не вижу принципиальной разницы для распараллеливания, цикл, или рекурсия. И даже наоборот. Переписывая алгоритм на vhdl мне намного проще работать с циклами, чем с рекурсией.
И независимо от языка рекурсия более ресурсоемка. Просто оно прячется под капот.
У рекурсии один несомненный плюс. Краткость записи и простота понимания.
В привычных нам языках программирования это так и есть - рекурсия более ресурсоёмка, но в функциональном - рекурсия это единственный способ, нет там циклов в принципе. Краткость записи - это далеко не плюс, и простоты понимания там тоже нет, напротив понять рекурсию довольно сложная задача т.к. требует задействования пространственного мышления. Это больше похоже на фокус, в котором мало движений но очень сложно понять и научиться его правильно выполнять.
Кстати, цикл на функциональном языке весьма ресурсоёмкая операция.
Да, я ошибся. Простым способом попарным обменом не обойтись. Нужен еще буфер размером с исходный.
левая половина от 0 до длина/2
А если длина будет нечетным числом?
Полагаю тут забыли округлить.
делал такую сортировку без рекурсии и буфера, по скорости страдает конечно, так как много проверок, но памяти требуется только sizeof(src[x]) для обмена.
а анимацию "Сортировка слиянием" вы сами делали или с просторов сети?
Да, обычным циклом будет экономнее. Я преследовал цель использовать рекурсию, поэтому без жертв не обошлось.
Гифки нашел в сети.
Если говорим об экономии, то экономия в чём? В тактах процессора очень врятли. Давненько уже до многих дошло прозрение что read-only участки памяти работают быстрее в целом, т.к. находятся исключительно в кеше ядра процессора и никуда больше не синхронизируются, что очень важно для многопоточных алгоритмов. Если вдруг другой процесс захочет прочитать ячейку которая могла изменится, он будет ждать пока кеш-линия будет выгружена из кеша в RAM, потом обратно в кеш того ядра где выполняется процесс... это очень огромные накладные расходы.
Сортировка слиянием через рекурсию