4 ms·
I disagree, because it is perfectly possible to sort without comparisons. For example, sorting a list of distinct integers is theoretically O(N). (radix sorting
by webkike 7y ago
I disagree, because it is perfectly possible to sort without comparisons. For example, sorting a list of distinct integers is theoretically O(N). (radix sorting)
- jeremysalwen 7y agoThat's not sorting, that's sorting distinct integers, which is a different problem. That's like saying multiplication can't have any lower bound because multiplying by zero is O(1).
- webkike 7y agoThat's not a definition supported by any literature I've read. Seems like you're moving the goalpost because you don't like the definition. For what it's worth, radix sort is listed on the wikipedia page for "Sorting Algorithms", and its runtime is listed as O(n * k) where k is the number of digits per number: https://en.wikipedia.org/wiki/Sorting_algorithm#Radix_sort https://en.wikipedia.org/wiki/Sorting_algorithm#Radix_sort