__merge_without_buffer() выполняет объединение на месте в качестве шага объединения сортировки слиянием на месте. Он принимает в качестве входных данных два диапазона данных [first, middle) и [middle, last), которые, как предполагается, уже отсортированы. Параметры len1 и len2 равны длинам двух входных диапазонов, а именно (middle - first) и (last - middle) соответственно.
Сначала выбирается элемент pivot . Затем он упорядочивает данные в порядке A1 B1 A2 B2, где A1 - это набор элементов в [first, middle), которые меньше, чем ось, A2 - это набор элементов в [first, middle), больший или равный pivot, B1 - это набор элементов на [middle, last) меньше, чем pivot, а B2 - набор элементов на [middle, last), больше или равный pivot. Обратите внимание, что данные изначально имеют порядок 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). Однако обратите внимание, что в mergesort это только один шаг: помните, что в mergesort вы сначала рекурсивно сортируете обе половины, а затем объединяете. Таким образом, рекуррентное отношение для времени выполнения слияния теперь равно:
T(N) = 2T(N/2) + O(N log N)
Включите это в Основную теорему , и вы получите, что сортировка слиянием теперь выполняется за O (N log 2 N) времени!
В качестве интересного финального пункта рассмотрим следующие три качества алгоритма сортировки на основе сравнения:
- В месте
- Стабильная
- Работает в O (N log N) время
Обычно вы можете получить только 2 из них одновременно - быстрая сортировка получает вас (1) и (3), mergesort получает вас (2) и (3), а сортировка на месте получает вас (1) и (2) ). Сортировки, не основанные на сравнении, такие как сортировка по счету, могут достигать всех 3, но эти сортировки могут сортировать только определенные типы данных. Возможно, существует сортировка на основе сравнения, которая достигает всех 3, но если она есть, я не знаю о ее существовании, и это почти наверняка намного сложнее.