Proving that Android’s, Java’s and Python’s sorting algorithm is broken

Re:Proving that Android’s, Java’s and Python’s sorting algor... by mark-r on Tuesday February 24, 2015 @04:16PM (#9103579)

I for one appreciate the fact that it's stable. That has definite benefits sometimes.

[ Parent | on HN ]

Re:Proving that Android’s, Java’s and Python’s sorting algor... by Retra on Tuesday February 24, 2015 @04:30PM (#9103660)

This 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?

[ Parent | on HN ]

Re:Proving that Android’s, Java’s and Python’s sorting algor... by TheLoneWolfling on Tuesday February 24, 2015 @05:19PM (#9103929)

Not 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.

[ Parent | on HN ]