Partial sort of std::list

Question

I have a linked list that I want to sort part of, eg:

std::sort(someIterator, otherIterator, predicate);

std::sort requires random-access iterators so this approach doesn't work. There is a specialisation std::list::sort, but that can only sort the entire list. I don't think I have enough access to the list members to write something myself.

Is there a way to do this without changing to, say, vector?

Answer 1

How about unhooking the part of the list that you want sorted, into a standalone list, then use the specialized list sort, then hook it back into the original list?

Answer 2

Yes, but you will have to use a merge sort.