Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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)


That'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).


That'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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: