4 ms·
I for one appreciate the fact that it's stable. That has definite benefits sometimes.
by mark-r 12y ago
I for one appreciate the fact that it's stable. That has definite benefits sometimes.
- Retra 12y agoThis is making me wonder if there is a theorem that would imply a stable sort on data that doesn't need it would be less efficient than a comparable unstable sort. There has to be a cost for stability, right?
- TheLoneWolfling 12y agoNot in asymtotic terms, at least. There exists a stable sorting algorithm that's O(1) axillary space, and O(n log n) worst-case time - wikisort. As both of those are provable lower bounds, this seems false.