Find exact position then insert or add then sort? Which is better?

Question

We have a big List of >1000 items with big classes (of the same type). The list is inserted or deleted very frequent. About 10 or 20, 30 items inserted at a time. With each item, I find exact position to insert using quick search algorithm. But I wonder if I add every items to the end of the list then do the sort using List.Sort (I believe that MS use quick sort algorithm) then it will be better: consume less CPU like current? I am using C#, .Net Framework 2.0.

Answer 1

There's rarely a general answer to questions like these. It depends very heavily on your scenario. But here's an intermediate suggestion between the two choices you bring up:

Sort the list of items to be inserted (this requires sorting 10 - 30 items based on your description). Then, insert these in order. Note that once you find the position to insert the first item, the position to insert the second item must be strictly after that location (and so on, for each subsequent item), so you don't need to search starting from the beginning again. The list being inserted into only needs to be searched through in this case as it would maintain its ordering after each insertion.