News for hackers. Stuff that matters.

A comment on Proving that Android’s, Java’s and Python’s sorting algorithm is broken. Parent comment

Re:Proving that Android’s, Java’s and Python’s sorting algor... by masklinn on Tuesday February 24, 2015 @10:12AM (#9100945)
Timsort is stable, has an O(n) best case and O(n log n) worst case and has specific optimisations for e.g. partially-sorted sequences.

It can also be implemented in-place to reduce space requirements from O(n) to O(log n).

> since it has linear space requirements (sorts in-place)

Quicksort has a O(log n) worst-case space requirement

[ Parent | on HN ]
Re:Proving that Android’s, Java’s and Python’s sorting algor... by IsTom on Tuesday February 24, 2015 @01:36PM (#9102570)
There is an in-situ quicksort that has the same asymptotic time bounds as the usual kind. It (kind of) encodes stack by shuffling some elements in unsorted data.
[ Parent | on HN ]
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 ]