3 ms·
> Most programs don't spend a noticeable amount time in sorting at all. I think a more important point is that most programs that depend on sorting data will u
by Jtsummers 8y ago
> Most programs don't spend a noticeable amount time in sorting at all.
I think a more important point is that most programs that depend on sorting data will use a data structure which can sort itself rather than trying to sort lists/arrays of such large numbers (especially when exceeding a certain threshold of data records). Consider if you're getting millions of records and need them in some order (potentially different from how they arrive), it makes more sense (especially with the IO delays) to spend the extra time on inserting into a sorted structure while waiting for the next piece of data to arrive. Interleaving the two activities, rather than waiting for all IO to finish and then sorting a massive list (forcing them to be serialized). The concurrent version can benefit from the inherent parallel nature of dealing with IO-bound and CPU-bound activities.
- jstimpfle 8y agoI'm not positive that most sorts are "online" with I/O that reads the data to be sorted. It's not what I wanted to imply anyway. The kind of I/O I meant is just generally time consuming I/O (large amounts of data, too many small requests, too much synchronization) that most applications are doing. For other, non-I/O intensive applications, most of them likely have bottlenecks other than sorting. In any case I wouldn't want to tie my data to an incremental sorting structure (like a search tree instead of a flat array) before I've ensured that this online aspect was critical. If it is not critical choosing a more complicated incremental structure is probably premature optimization which constrains the project structure, and thus is likely to negatively affect performance and maintainability in the end.