STL __merge_without_buffer алгоритм?

__merge_without_buffer() выполняет слияние на месте как этап слияния сортировки слиянием на месте. Он принимает в качестве входных данных два диапазона данных [first, middle) и [middle, last), которые, как предполагается, уже отсортированы. Параметры len1 и len2 равны длинам двух входных диапазонов, а именно (middle - first) и (last - middle) соответственно.

Сначала он выбирает элемент вращаться. Затем он перестраивает данные в A1 B1 A2 B2 порядке, где A1 есть множество элементов в [first, middle), которые меньше, чем стержень, A2 представляет собой набор элементов в [first, middle) больше или равно к оси поворота, B1 есть множество элементов в [middle, last) меньше точки поворота, а B2 - это набор элементов в [middle, last), больший или равный оси поворота. Обратите внимание, что данные изначально находятся в порядке A1 A2 B1 B2, поэтому все, что нам нужно сделать, это превратить A2 B1 в B1 A2. Это при вызове std::rotate(), который делает именно это.

Теперь мы отделили элементы, которые меньше точки поворота (A1 и B1), от тех, которые больше или равны оси поворота (A2 и B2), поэтому теперь мы можем рекурсивно объединить два поддиапазона A1 A2 и B1 B2.

Как выбрать точку опоры? В рассматриваемой мной реализации он выбирает медианный элемент из большего поддиапазона (т.е. если [first, middle) имеет больше элементов, чем [middle, last), он выбирает медианное значение [first, middle); в противном случае он выбирает медианное значение [middle, last)). Поскольку поддиапазоны уже отсортированы, выбор медианы тривиален. Этот выбор поворота гарантирует, что при рекурсивном объединении двух поддиапазонов, каждая подзадача является не более чем 3/4 от размера текущей проблемы, потому что в худшем случае, по крайней мере 1/4 элементов больше или меньше, чем стержень .

Какое время работы у этого? Вызов std::rotate() занимает O (N) времени, и мы делаем два рекурсивных вызова себе. Это соответствует времени работы O (N log N). Однако обратите внимание, что это только один шаг в сортировке слиянием: помните, что в сортировке слиянием вы сначала рекурсивно сортируете обе половины, а затем объединяете. Таким образом, рекуррентное соотношение для времени выполнения сортировки слиянием теперь выглядит следующим образом:

T(N) = 2T(N/2) + O(N log N)

Подключите это к Основная теорема, и вы получите, что сортировка слиянием теперь выполняется за время O (N log² N)!

В качестве последнего интересного момента рассмотрим следующие три качества алгоритма сортировки на основе сравнения:

1. На месте
2. Стабильный
3. Работает за O (N log N) раз

Обычно вы можете получить только 2 из них одновременно - быстрая сортировка дает вам (1) и (3), слияние дает вам (2) и (3), а сортировка слияния на месте дает вам (1) и (2). Сортировки, не основанные на сравнении, такие как сортировка по счетчику, могут обеспечить все 3, но эти сортировки могут сортировать только определенные типы данных. Возможно, существует сортировка на основе сравнения, которая выполняет все три, но если есть, я не знаю о ее существовании, и это почти наверняка намного сложнее.