7

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?

Benoit
  • 76,634
  • 23
  • 210
  • 236
Alexander Bird
  • 38,679
  • 42
  • 124
  • 159

3 Answers3

10

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)²).

Community
  • 1
  • 1
Frédéric Hamidi
  • 258,201
  • 41
  • 486
  • 479
  • 1
    -1 The question is, is the scenario the OP proposed the worst case for either of the algorithms? Comparing worst case complexities does not make sense when a specific scenario is considered. – Björn Pollex Oct 20 '10 at 09:18
  • 2
    @Space_c0wb0y disagree, the question seems to be more general and later uses the scenario as an example, that said the complexities do not necessarily mean inplace_merge will never be slower than sort, and this answer doesn't consider stability – jk. Oct 20 '10 at 09:29
  • Thanks. The only other thing I'm putting in this answer is the fact that inplace_merge is stable, whereas sort (not stable_sort) is unstable in how it sorts. But what you had answered the question. I should have fully read the "manual" at cplusplus.com :) – Alexander Bird Oct 25 '10 at 19:41
  • Looking at the 98 standard, 25.3, `sort` has an average case of N log N comparisons, while `stable_sort` does at most N (log n)^2 comparisons. (The footnote suggests that those who are worried about worst-case performance should use `stable_sort` or `partial_sort`.) These requirements seem to be kept in the C++0x draft I've got. – David Thornley Oct 25 '10 at 20:09
  • @David, yes, that's also what MSDN says. [C++ Reference](http://www.cplusplus.com/reference/algorithm/sort/) mentions a worst case of O(N²), though, depending on the algorithm. – Frédéric Hamidi Oct 25 '10 at 20:15
  • @Frédéric Hamidi: That's not an authoritative reference (neither is MSDN, of course), but it should always be possible to use `std::stable_sort` to limit worst-case performance to O(N (log N)^2), which is better than O(N^2). At least in a Standard-conforming implementation. – David Thornley Oct 25 '10 at 20:36
  • @FrédéricHamidi I coundt find any where mentioned the worst case is O(N^2). is it your conclusion based on the page you referred? – Azzurro94 Jan 08 '22 at 18:46
  • 1
    @Azzurro94 Until C++11, `std::sort` was required to be O(N log N) on average, but did not define the worst case. So quick sort could be used, which has O(N^2) worst case. Since C++11, the standard fixed the complexity to be O(N log N). Many implementations use some variants of quick sort/heapsort. See [this](https://en.cppreference.com/w/cpp/algorithm/sort#Complexity). – Ale Jun 12 '22 at 23:07
5

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.
Benoit
  • 76,634
  • 23
  • 210
  • 236
  • _"`inplace_merge` must be implemented in a different way and will therefore probably be more efficient"_. That's wrong. The standard does not enforce a specific algorithm for `inplace_merge`, only the bottom-line effect and complexity of the algorithm. Also, in fact `sort` will _probably_ be more efficient than `inplace_merge`. That is, `inplace_merge` has a better worst-case guarantee than `sort`, but `sort` has a better performance from a statistical standpoint, over a large set of various inputs. This is not a Standard guarantee though:The emphasis is on _probably_. – wilhelmtell Oct 29 '10 at 16:10
  • @wilhelmtell, what I mean when I say *must* is like in *there must be something*. – Benoit Oct 29 '10 at 16:13
  • @wilhelmtell: I would expect `inplace_merge` to always be faster than `std::sort`. The standard does not mandate exact performance (the compiler can add arbitrary sleep statements), but since compiler writers aren't intentionally writing bad code, the obvious implementation of `inplace_merge` will never be worse than any implementation of `std::sort`. – David Stone Apr 26 '14 at 17:47
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).

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

Buhake Sindi
  • 87,898
  • 29
  • 167
  • 228
  • -1 Same as for Frèdèric: Comparing the worst case complexities of the algorithm does not make sense when a specific scenario is considered, that might not be the worst case for any of the algorithms. – Björn Pollex Oct 20 '10 at 09:20
  • Thanks, strange, I still got the -1, and my score is still the same (on 4493)...just saying,.....lol – Buhake Sindi Oct 20 '10 at 10:17