That 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

That 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