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.