как сортировать два "половинных" массива в сортировке слиянием?
в этом видeо увидел на 0:45 - 0:56 то, что нужно отсортировать половинки массива, но автор не указал как. По идее, время выполнения сортировки слиянием равно n*log(n), но что, если два этих половинных массивов мы будем сортировать разными методами? Тогда, вроде, не будет достигнуто заявленное время (как мне кажется).
Вопрос: каким методом нужно сортировать два "половинных" массива?
Ответы (1 шт):
Автор решения: Mikhailo
→ Ссылка
Идея именно в том, что каждая половинка сортируется тем же методом - сортировкой слияния. Именно отсюда и вытекает сложность алгоритма O(N*log(N)).
Что до рекурсия-итерация: да, в общем случае рекурсия медленнее (не в смысле сложности алгоритма!) из-за вызова функции, но эта разница не так уж велика, а оптимизатором часто просто убирается вовсе.