I'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 jus

I'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.