Сортировка путем объединения алгоритмов сортировки вставками и сортировки слиянием.

Сортировка вставками: массив фактически разделен на отсортированную и несортированную части. Значения из несортированной части выбираются и помещаются в правильную позицию в отсортированной части.
Преимущества: Ниже приведены преимущества сортировки вставками:

• Если размер сортируемого списка невелик, сортировка вставками выполняется быстрее.
• Сортировка вставками занимает время O(N), когда элементы уже отсортированы
• Это алгоритм на месте O (1), вспомогательное пространство не требуется.

Сортировка слиянием: Сортировка слиянием — это алгоритм «разделяй и властвуй». Он делит входной массив на две половины, вызывает себя для этих двух половин, а затем объединяет две отсортированные половины.

Преимущества: Ниже приведены преимущества сортировки слиянием:

• Разделение основной проблемы на подзадачи не требует значительных затрат.

Из приведенных выше двух сравнений преимущества обоих алгоритмов сортировки могут быть объединены, и результирующий алгоритм будет иметь временную сложность O(N[K+log(N/K)]). Ниже приведен вывод временной сложности этого комбинированного алгоритма:
Пусть, нет. элементов в списке = N
Разделить :

• Сначала мы разделим эти N элементов на (N/K) групп размера K

Сортировка :

• Для каждого подразделения подмассива размера K выполните операцию сортировки вставками, чтобы отсортировать этот подмассив.
• Общая стоимость сортировки вставками для одного блока из K элементов:
  • В лучшем случае: O(K)
  • В худшем случае: О(
• Поскольку существует (N/K) таких блоков размера K, мы получаем общую стоимость применения сортировки вставками как:
  • В лучшем случае: (N/K) * K = O(N) <– (1)
  • Для наихудшего случая: (N/K) * K^{2} = O(NK) <– (2)

Слияние :

• После применения сортировки вставками по (N/K) группирует каждый из K отсортированных элементов
• Для слияния этих (N/K) групп:

• Допустим, мы делаем i итераций сортировки слиянием. Итак, чтобы цикл остановился, нам нужно приравнять как:
• (2 ^ я) * К = Н
• (2 ^ я) = Н/К
• i*log(2) = log(N/K) Берем журнал с обеих сторон
• я = журнал (Н/К)
• Стоимость слияния = O(N)
• Общая стоимость слияния = количество итераций * стоимость итерации
  • = лог(Н/К)*Н
  • = Н*лог(Н/К)
  • = O(N*Log(N/K)) <– (3)

Общая стоимость алгоритма (вставка + слияние) составляет:

• В лучшем случае: N+Nlog(N/K) <– из (1) и (3)
• Наихудший случай: NK + Nlog(N/K) <– из (2) и (3)

Если K = 1, то это полная сортировка слиянием, которая лучше с точки зрения временной сложности.
Если K = N, то это полная сортировка вставками, которая лучше с точки зрения пространственной сложности.