3 ms·
This phrase is misleading: The fastest time to sort an integer array is O(N) It could be interpreted as generally applicable. The proposed method uses reverse
by rhardih 10y ago
This phrase is misleading:
The fastest time to sort an integer array is O(N)
It could be interpreted as generally applicable. The proposed method uses reverse-indexed flagging, an approach which isn't really feasible if element values are very large.
Generally, the lower bound for any comparison based sorting algorithm is Ω( n log( n )).
- EllipticCurve 10y agoThat is true. Just want to add, that the lower bound for sorting is O(n log(n)) for comparison based sorting in infinite universes. The comparison based factor rules out sorting of any element, that can not be reduced to an integer. Infinite universes in sense, that we don't know about the elements/element-range beforehand. Sorting in θ(n+k) w.c. and a.c. (most of the time this is equal to O(n)) is possible for finite boundaries that allows for countingsort or bucketsort (radixsort uses countingsort internally). Some implementations of those algorithms in Python: https://github.com/MauriceGit/Advanced_Algorithms https://github.com/MauriceGit/Advanced_Algorithms
- sangupta 10y agoAgreed about the phrase thing - updated the phrase accordingly to say: "Fastest sorting of bounded integers"