C ++ STL :: в чем разница между inplace_merge и sort

Question

Насколько я могу судить, inplace_merge делает то же самое, что и sort, за исключением того, что он работает только при определенных обстоятельствах (когда контейнер уже состоит из двух отсортированных частей).

Другими словами, есть лиразница между этими двумя значениями:

int first[] = {1,3,5,7};
int second[] = {2,4,6,8};
vector<int> v(8);
vector<int>::iterator it;
copy(first,first+4, v.begin());
copy(second,second+4, v.begin()+4);

inplace_merge(v.begin(), v.begin()+4, v.end())

.

int first[] = {1,3,5,7};
int second[] = {2,4,6,8};
vector<int> v(8);
vector<int>::iterator it;
copy(first,first+4, v.begin());
copy(second,second+4, v.begin()+4);

sort(v.begin(), v.end())

Единственная разница будет в эффективности?

Answer 1

Их сложность не одинакова:

• sort () имеет наихудший случай O(N²), в зависимости от алгоритма сортировки, используемого вашей реализацией STL.

• inplace_merge () имеет наихудший случай O(N*log(N)) и лучший случай O(N-1), поэтому он никогда не будет медленнее sort() (с теми же данными).

Кроме того, как указывали другие, inplace_merge() является стабильным : он сохраняет порядок элементов, ключ сортировки которых одинаков,sort() не гарантирует этого. stable_sort () делает, и его наихудшая сложность равна O(N*log(N)²).

Answer 2

Два различия:

• стабильность : inplace_merge - это стабильный алгоритм (он будет сохранять одинаковые элементы в одном порядке оба в пределах поддиапазонов и между вами двумя исходными диапазонами).
  Таким образом, может иметь место небольшое различие в результате, когда вы работаете с контейнерами не примитивных типов или когда ваша функция сортировки вытеснена.Конечно, с контейнером int egers вы не заметите никакой разницы:)
• эффективность : как вы сказали, учитывая тот факт, что у вас уже есть два отсортированных подмножества, inplace_merge должны быть реализованы другим способом и, следовательно, вероятно, будут более эффективными.Единственный факт, что эта функция существует, говорит о многом.

Answer 3

Метод sort сортирует 2 отсортированных элемента в диапазоне ( первый , последний ) в порядке возрастания.inplace_search объединяет 2 отсортированных диапазона ( первый , средний ) и (средний, последний) в объединенный отсортированный диапазон ( первый , последний ).

• сортировка
• inplace_merge

---

Для inplace_merge дочтобы быть эффективными, 2 поддиапазона должны быть отсортированы (в этом разница).Кроме того, inplace_merge теоретически нестабильно , (но стабильно в C ++), но для этого требуется эффективная память (последняя - первая) - 1 сравнение, иначе это похоже на сортировку (которая делаетO (n log n) сравнений).