24. Расскажите про сортировку слиянием.

Основана на парадигме разделяй и властвуй.

Будем делись массив пополам, пока не получим множество массивов из одного элемента. После чего выполним процедуру слияния: поддерживаем два указателя, один на текущий элемент первой части, второй – на текущий элемент второй части.

Из этих двух элементов выбираем минимальный, вставляем в ответ и сдвигаем указатель, соответствующий минимуму.

Так сделаем слияния массивов из 1го элемента в массивы по 2 элемента, затем из 2х в 4 и т.д.
Слияние работает за O(n), уровней всего log(n), поэтому асимптотика O(n*log(n)).

Предыдущий вопрос: 23. Расскажите про быструю сортировку.

Следующий вопрос: 25. Расскажите про бинарное дерево.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне