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.