@iurnah Hi iurnah. You were right. Sorting the array takes O(nlogn). Inside the for loop, both search and insert take O(logn), and we do this for each element so the time complexity will be O(nlogn). In summary, the overall complexity will be O(nlogn).
@dengzhizhang this is because multiset::iterator is a bidirectional iterator rather than random access iterator. Bidirectional iterator only supports incremental and decremental operations and std::distance yields O(n) rather than O(1) time complexity when used to compute two iterators' distance.