Временная сложность O(nlogn) в худшем, среднем и лучшем случае, где n — количество элементов в массиве: Пространственная сложность O(n), так как для слияния двух подмассивов требуется временный массив того же размера, что и исходный. Идея Сортировка слиянием является примером алгоритма "разделяй и властвуй": Функция sort 1. Условие выхода из рекурсии: если массив содержит ноль или один элемент, он уже отсортирован, возвращаем его. 2. Находим середину массива и делим его на два подмассива: left и right...

Ей уже 60 лет, но она до сих пор работает быстро Это статья о реализации одного из алгоритмов сортировки. Эти алгоритмы считаются классикой информатики: разработчиков могут спросить об этих алгоритмах на собеседовании, а сами алгоритмы помогают ощутить силу автоматики и алгоритмов. Сегодня пощупаем один из таких алгоритмов. Ранее в статьях мы рассказали про два вида сортировки: Эти сортировки относятся к простым видам алгоритмов — надёжным, но неоптимальным по скорости и затратам памяти. Гораздо...

В данной реализации алгоритма быстрой сортировки мы начинаем с проверки того, что длина массива меньше или равна 1. Если это так, мы просто возвращаем массив, поскольку он уже отсортирован. Далее мы выбираем поворотный элемент, взяв средний элемент массива. Затем мы создаем два среза для хранения элементов, меньших, чем поворотный, и элементов, больших, чем поворотный. Перебираем массив, пропуская поворотный элемент. Если элемент меньше поворотного, мы добавляем его в левый фрагмент...

Заметки: Эта сортировка намного быстрее сортировки выбором (когда делим пополам всегда). И используется во многих библиотеках (например, метод sort). Но и понять её гораздо сложнее. Тут уже прям придётся вникать. Сложность зависит от выбора опорного элемента. В худшем будет O(n^2). В лучшем и в среднем — O(n logn). Существует ещё сортировка слияниям и она по сложности примерно такая же. Тогда почему быстрая сортировка считается...