In C++, why there is a requirement that lists must be sorted before merging

Question

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

Answer 1

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.

Answer 2

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

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

Answer 3

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.