2. Сортировки Merge sort Quick sort

Описание

Merge sort — алгоритм сортировки слиянием, Quick sort — алгоритм быстрой сортировки. Оба используют принцип «разделяй и властвуй»: массив рекурсивно делится на несколько мелких частей, которые затем упорядочиваются и объединяются.

Merge sort
Принцип работы: массив рекурсивно делится на две равные (или почти равные) части до тех пор, пока каждый подмассив не будет состоять из одного элемента. Затем подмассивы объединяются в отсортированном порядке, начиная с самых маленьких подмассивов.

Сложность: временная сложность — O(n log n), где n — количество элементов в массиве.

Применение: алгоритм подходит для больших данных, может эффективно работать с данными, которые не помещаются в оперативную память. Также используется для внешней сортировки на жёстких дисках.

Особенности:
Стабильность: если в исходном массиве было два одинаковых элемента, то в отсортированном списке они останутся в том же относительном порядке, в каком были изначально.
Требует дополнительной памяти на этапе слияния, где нужно создать временные списки для хранения отсортированных половин и итогового объединённого списка.