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