В классическом алгоритме сортировки слиянием обычно делят входной массив до тех пор, пока они не получат несколько одноэлементных подмассивов до объединения элементов вместе.Но хорошо известно, что вы можете модифицировать этот алгоритм сортировки слиянием, разбивая массивы, пока у вас не будет, скажем, k подмассивов, каждый из которых имеет размер n / k (n - исходная длина массива).Затем вы можете использовать сортировку вставками для сортировки каждого из этих k подмассивов и объединения их с помощью подпрограммы слияния.
Интуитивно я думаю, что в некоторых случаях это должно быть лучше, чем просто сортировка слиянием, поскольку сортировка вставкой выполняется быстро.небольшие массивы.Но я хочу точно выяснить, когда этот гибридный алгоритм лучше, чем обычный алгоритм сортировки слиянием.Я не думаю, что было бы лучше для малых k, потому что, когда k приближается к 1, мы просто использовали бы алгоритм сортировки вставкой.Я думаю, что есть какое-то оптимальное соотношение n / k, но я не совсем уверен, как его найти.
Любая помощь приветствуется.