C++ STL:: what's the difference between inplace_merge and sort

Question

As far as I can tell, inplace_merge does the exact same thing as sort, except it only works in certain circumstances (When the container is already in two sorted parts).

In other words, is there an difference between these two:

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())

Is the only difference going to be efficiency?

Answer 1

Their complexity is not the same:

• sort() has a worst case of O(N²), depending on the sorting algorithm used by your STL implementation.

• inplace_merge() has a worst case of O(N*log(N)) and a best case of O(N-1), so it will never be slower than sort() (with the same inputs).

Also, as others have pointed out, inplace_merge() is stable: it preserves the ordering of items whose sort key is the same. sort() does not guarantee this. stable_sort() does, and its worst-case complexity is O(N*log(N)²).

Answer 2

Two differences:

• stability: inplace_merge is a stable algorithm (it will keep equal items in the same order both within subranges and between you two original ranges).
  So, there might be a slight difference in the result when you deal with containers of non-primitive types, or when your sort function is extricated. Of course, with container of integers, you will not notice any difference :)
• efficiency: as you told, given the fact that you already have two sorted subsets, inplace_merge must be implemented in a different way and will therefore probably be more efficient. The single fact that this function exists tells much.

Answer 3

The sort method sorts 2 sorted elements in the range (first, last) in ascending order.
inplace_search merges the 2 sorted range (first, middle) and (middle, last) into a combined sorted range (first, last).

• sort
• inplace_merge

---

For inplace_merge to be efficient, the 2 subranges must be sorted (that's the difference). Additionally, inplace_merge is theoretically unstable, (but stable in C++) but it requires efficient memory to do (last - first) - 1 comparisons else it's similar to sort (which does O(n log n) comparisons).