У нас есть 3 варианта сортировки слиянием.
Есть ли какие-нибудь из этих адаптивных алгоритмов? Например, если массив отсортирован, они воспользуются преимуществом отсортированного порядка.
По моему мнению, независимо от того, отсортирован массив или нет, сортировка слиянием все равно будет сравниваться, а затем слиться. Итак, ответ: ни один из них не является адаптивным.
Я правильно понимаю?
Сортировка естественным слиянием является адаптивной. Например, он выполняет только один проход по отсортированному массиву и выполняет N сравнений.
И сверху вниз, и снизу вверх не адаптивны, они всегда выполняют O (NlogN) операций.
Сортировка слиянием - это реализация алгоритма «разделяй и властвуй». Вам нужно разделить весь массив на подмассивы. Например, [1, 3, 5, 6, 2, 4,1 10] делится на [1 3 5 6] и [2 4 1 10]. [1 3 5 6] делится на [1 3] и [5 6]. Теперь, когда отсортированы и [1 3], и [5 6], процедура обмена не требуется.
Так что есть хотя бы небольшая сложность, если массив отсортирован
По мне, независимо от того, отсортирован массив или нет, сортировка слиянием все равно будет использоваться для сравнения
Я не думаю, что можно выполнять сортировку без каких-либо сравнений и экономить память, если входные данные еще не отсортированы или содержат информацию о том, какой порядок сортировки следует выполнять. Самый быстрый алгоритм сортировки имеет временную сложность O (n log (n)) (существуют методы сортировки, такие как сортировка шариков. Я не рассматриваю его здесь, поскольку это не оптимальный метод тиски памяти)
P.S быстрая сортировка включает сравнения (но адаптивна), и в худшем случае она делает около O (n ^ 2) сравнений.
P.P.S Radix sort, counting sort и bucket sort - некоторые примеры адаптивной сортировки;
