4

In the C++, list data structure has a merge function which basically removes all objects in the source list and put into destination list. 

// source list will be empty after this operation
destinationList.merge(sourceList);

According to tutorials/examples, lists must be sorted before merging operation. 

destinationList.sort();
sourceList.sort();
destinationList.merge(sourceList);

I confused because if there is a requirement of sorting lists, why C++ doesn't enforce it by calling sort function in the merge function?

Another thing, I can first merge unsorted lists, then I can sort merged list, isn't this same?

destinationList.merge(sourceList);
destinationList.sort();
Cœur
  • 37,241
  • 25
  • 195
  • 267
Validus Oculus
  • 2,756
  • 1
  • 25
  • 34
  • 1
    If order is not important, you may use `dst.insert(dst.end(), src.begin(), src.end()); src.clear();` – Jarod42 May 15 '14 at 15:02
  • 2
    The complexity of the algorithm is not the same if `merge` should sort first. – Jarod42 May 15 '14 at 15:04
  • 2
    Some lists may be already sorted so there is no need to call sort before the merge. If STL calls sort before the merge then it would be performing an unnecessary sort. Basically the code does what it says on the tin: sort sorts and merge merges. It is up to you to put in the intelligence i.e. sort before the merge. – cup May 15 '14 at 15:06
  • I would point out that `list::sort` may only be O(n*log(n)) in terms of comparisons, but in terms of iterations it is inefficient (going back and forth in memory) compared to a Random Access Container such as `vector` or `deque`. I refer you to [How can I efficiently select a standard library container in C++11](http://stackoverflow.com/questions/10699265/how-can-i-efficiently-select-a-standard-library-container-in-c11/10701102#10701102) as quick guide on how to pick the most suitable container. – Matthieu M. May 15 '14 at 15:50

3 Answers3

16

why there is a requirement that lists must be sorted before merging?

The purpose of merge is to merge two sorted lists to create a new sorted list, without the overhead of performing another sort. Merging can be done in linear time, while sorting is O(n*log(n)).

why c++ doesn't enforce it by calling sort function in the merge function ?

Because, if the list is already sorted, that would be horribly inefficient.

Another thing, i can first merge unsorted lists, then i can sort merged list, isn't this same ?

No. The merge algorithm requires that the inputs be sorted, and produces a sorted list from them. It works by comparing the first elements of the input lists, taking the lower one, and appending that to the output list.

You could achieve the same thing by appending the two lists then sorting the result; but again that would be inefficient if the lists are already sorted.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • how comes that I can merge two unordered lists `listl1 {5,4,3,2,1}` and `listl2 {10,9,8,7,6}` ? I mean where does it states how or what ordered means? ascendent? descendent? – Cătălina Sîrbu Apr 17 '20 at 15:02
  • 1
    @CătălinaSîrbu is the result of that merge what you would expect? THe order is decided by the comparitor passed through the template which is `std::less` by default, this compares using the `operator<()` on the elements. – ratchet freak Apr 17 '20 at 15:56
4

One of the driving priniciples of C++ design is "Don't pay for what you don't use".

You are possibly referring to the requirement of

§23.3.5.5 list operations

void merge(list& x);

void merge(list&& x);

template void merge(list& x, Compare comp);

template void merge(list&& x, Compare comp);

22 Requires: comp shall define a strict weak ordering (25.4), and both the list and the argument list shall be sorted according to this ordering.

What happens in an actual implementation is that the merge operation doesn't just take two lists and copies the elements from one into another, it merely exploits the underlying representation of some kind of linked list like structure, and relinks elements from one list into another. It will do this by going through both lists and taking the next bigger element. Since the lists are both sorted already, it can do this by always just looking at the first element of both lists. An operation in linear time O(n).

Would you always concatenate them (an operation possible by a splice like operation in constant time) and then sort them, the complexity would raise to O(n log n). This is undesired if you already have sorted lists.

If you don't, then splicing them together, and sorting afterwards is the thing you want to do.

Offering all these functionalities seperately (splice, merge, sort), the user can chose what is the most efficient thing to combine his lists, based on his knowledge of them being already sorted or not.

PlasmaHH
  • 15,673
  • 5
  • 44
  • 57
1

A slightly different take assuming you mean 'combining' rather than 'merging' here.

There is no requirement that lists be sorted before they are combined together. There are 3 separate slightly different ways to combine lists depending on your requirements

Merging sorted lists:

list1.merge( list2 ) // Complexity linear. Assumes list1 & list2 are sorted

Moving all elements of a list into another:

list1.splice( std::end( list1 ), list2 ) //Complexity: constant

Copying some elements of one list into another:

list1.insert( it1, it2 )// Complexity: linear, it1 & it2 are iterators pointing into list2

So infact the C++ standard provides multiple algorithms each with the optimal complexity for that particular task.

indeterminately sequenced
  • 626
  • 6
  • 17