Are there any algorithms that benefit in time complexity placing each item into a list in in sorted order as they are generated vs generating the whole list and just using quicksort on the completely unsorted finished product?
I'm thinking no, since if that was the case then you could just iterate over an unsorted list using this algorithm to beat quicksort, but I was wondering if I was wrong.
If you are not adamant about using a list then Binary Search Tree has a O(log(n)) insertion complexity and will be in order by the end of the insertions. There will be overhead though and thus use this approach only if you absolutely need to know the sorted order of elements after each insertion.
Say a situation where you need to find the index of the inserted element after each insertion. Note that insertion in a sorted list at desired index would take O(n) since you'd have to shift greater elements to the right to make space.
Per OP's requests, moving my comment to the answer. In the case of searching, the assumption of being presorted doesn't get us anything (while it does in the search problem). The most efficient way to find the correct place for an element in a sorted list is binary search which is O(log n), you do this for n elements. You still get O(nlgn). We have very strong proof that we CANT do better than O(nlgn) for comparison-based certain sorting. Please do note, there are algorithm's that we know to run in O(n) on average with worst case still being O(nlgn) such as Smooth Sort. However there is a difference between being presorted vs. items arriving in random order and being inserted a sorted sublist
You can read a little bit more about these:
Generic and practical sorting algorithm faster than O(n log n)?
https://cs.stackexchange.com/questions/80458/can-we-create-faster-sort-algorithm-than-on-log-n
Of course you can do a random algorithm where you randomly sort & hope for the best. We do have techniques that we can use to manipulate the probabilities such that the probability of getting the element we need next is very close to 1, and probability of picking the other elements are very very close to 0. This is how we get O(√N) search in an unsorted list in quantum search (there is some recent evidence that this might be achievable in regular computers but haven't been successfully implemented yet)
if we one day find a more efficient algorithm to sort, it will be one that magically does it without comparing the elements. This invariant is so strong that even with quantum sorting we don't know how to do better than O(nlgn) at this point.There are exceptions to this in space-bounded sorting
You could try adding each item, as it is generated, into a heap -- stick it on the end and "bubble" upwards into place. When you are done generating, you can read the items out in sorted order -- "popping" each one from the top of the heap. Or, if you want the list sorted, complete the heap sort -- which comes to the same thing.
