14 ms·

I think you might mean selection sort, which picks out elements from the original in sorted order one at a time. Insertion sort has partial results early as we

I think you might mean selection sort, which picks out elements from the original in sorted order one at a time. Insertion sort has partial results early as well, but they probably wouldn't be as useful, the only thing you could report early would be "here's the sorted order of the first k elements in the list" (as opposed to the first k elements in sorted order from the whole list, that selection sort gives you). If you really did want online output like that, I think you'd want to look at heapsort instead. If you compare the worst-case you have O(n) time to prepare the heap (once at the start) and then O(lg n) time to produce each single element of the answer. Selection sort you'd require O(n) time to produce each element. Selection sort doesn't win out in average or best case either. The best you could really hope for is it to win on constant factors, but it'd be hard for realistic inputs.

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 ago
  Ah, 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 ago
    Yes, 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.

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 ago
Ah, 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 ago
  Yes, 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.