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

Question

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

In other words, is there a difference between the 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()) 

Will there be a difference only in efficiency?

Answer 1

Their complexity is not the same:

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

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

In addition, as others have noted, inplace_merge() stable : it maintains the order of the elements whose sort key is the same. sort() does not guarantee this. stable_sort () , and its worst complexity is O(N*log(N)²) .

Answer 2

Two differences:

• stability : inplace_merge is a stable algorithm (it will store equal elements in the same order both inside the subranges and between you two source ranges).
  Thus, there may be a slight difference in the result when you are dealing with containers of non-primitive types or when your sort function is unloaded. Of course, you won’t notice any difference with the int egers container :)
• efficiency : as you said, given the fact that you already have two sorted subsets, inplace_merge should be implemented differently and therefore will probably be more efficient. The only fact of the existence of this function says a lot.

Answer 3

The sort method sorts 2 sorted items in a range (first, last) in ascending order.

inplace_search combines 2 sorted ranges (first, middle) and (middle, last) into a combined sorted range (first, last).

• sort
• inplace_merge

---

For inplace_merge to be effective, 2 subranges must be sorted (which is the difference). Also, inplace_merge theoretically unstable , but stable in C ++), but it requires efficient memory (last - first) - 1 else comparison, it looks like sort (which makes O (n log n)).