3 ms·
I think the poster means you aren't given the completed set. Elements come dribbling in a few at a time. With insertion sort, you're able to say, "this is the s
by nwallin 7y ago
I think the poster means you aren't given the completed set. Elements come dribbling in a few at a time. With insertion sort, you're able to say, "this is the sorted list at the time we know it right now." Obviously when you get the next element, you don't have a sorted list anymore; you have a sorted list and one extraneous element. But then you apply insertion sort iteration and have a sorted list again.
- kadoban 7y agoAh, yes that's true, good point. If that is the goal, BST sort might be a good idea as well (put elements into a balanced binary search tree as you receive them). Not _quite_ the same semantics (you don't have an array exactly at each step), but much faster asymptotics and should be able to answer any queries you'd be doing anyway.
- nwallin 7y agoYes, exactly. One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and pointer indirection being slow, even though random inserts into arrays are slow. Especially for small sets or when reads greatly outnumber writes. Boost has flat_map and flat_set for this.