Thread: List Sorting Question

Originally Posted by Polystyrene

My question is would it be faster to make a smaller list containing the new data structures, sort it, and then merge it into the larger list.

Yes I believe so, particularly when the number of items being inserted is a fair bit less than the number of items already inserted. Merging-in a sorted run being faster than merging those items in individually, is in fact the principle behind the Strand-Sort sorting algorithm.
Before I got to that sentence, this was in fact going to be my exact suggestion. This assumes a std::list is the best container for the job of course.

If your list is never allowed to have duplicates, then another option is to use a std::set instead of a std::list. The main difference being that it is always sorted. There's also multiset if you do have duplicates.

Originally Posted by Polystyrene

Ok so I tried using the lower_bound function to find the iterator where it should be inserted as whiteflags suggested. However, the program becomes very slow and according to the profiler I am spending 70% of my time performing the iterator++ operator.

As it would. There is not much advantage in using lower_bound with iterators that are not random access. Its first step is to count the number of items in the range, i.e. evaluate std::distance(begin, end) which means iterating over the entire list. So it's not just that it may end up iterating over the entire list, it does explicitly iterate over the entire list before it even starts doing any comparisons. Typically even a linear search is faster than this would be. But if the comparison operator is far slower than iterating and the list is short enough, then it can be a win, but basically it was a poor suggestion.

Originally Posted by whiteflags

The whole point is that it is faster to sort all the unsorted data once than to ensure that the list is always sorted.

I should clarify that. It just boils down to, don't sort the data it you don't need to access it in sorted order just yet. It does not means that it is faster to re-sort the whole thing each time. On the flipside, not all of the effort it sorting some of the data before it is needed sorted is lost, especialy if you dont throw away the information about which portion is already sorted.

Originally Posted by whiteflags

To loosely answer your question merging two lists and getting a sorted list out of it is a sort, and would be as fast as most other sorts. The only way to know in this case is to profile both strategies that you mention.

That's not the only way to know. A Big-Oh notation anaylsis shows that if the number of items being added is sufficiently less than the number of items already present, then it is faster. I've done this previously and submitted it as an optimisation to the Loki library authors some time ago for their assoc_vector class. It tends toward O(n), whereas a full sort would be O(n*logn).