Сортировка слиянием
Сортировка слиянием — интерактивный эксперимент из приложения «Алгоритмы в действии», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
Сортировка слиянием делит массив пополам, сортирует каждую половину тем же способом (рекурсия), а затем сливает две отсортированные половины: всегда берёт меньший из двух первых элементов. Деление пополам даёт log₂ n уровней, и на каждом уровне обрабатываются все n элементов, поэтому время всегда O(n log n). При равенстве берётся левый элемент, поэтому сортировка устойчива.
Попробуй: Попробуй обратный, а затем почти отсортированный массив того же размера. Число сравнений почти не меняется — порядок входных данных почти не важен.
Частые вопросы
Что показывает эксперимент «Сортировка слиянием»?
Сортировка слиянием делит массив пополам, сортирует каждую половину тем же способом (рекурсия), а затем сливает две отсортированные половины: всегда берёт меньший из двух первых элементов. Деление пополам даёт log₂ n уровней, и на каждом уровне обрабатываются все n элементов, поэтому время всегда O(n log n). При равенстве берётся левый элемент, поэтому сортировка устойчива.
Как попробовать «Сортировка слиянием»?
Попробуй обратный, а затем почти отсортированный массив того же размера. Число сравнений почти не меняется — порядок входных данных почти не важен.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.