3 ms·
No, the bound is not on the performance of the sorting algorithm, but rather on the minimum number of comparisons required
by webkike 7y ago
No, the bound is not on the performance of the sorting algorithm, but rather on the minimum number of comparisons required
- wongarsu 7y agoI would argue that "number of comparisons" is just the popular performance metric. Of course in reality we care about execution time, and in order to go from "we need O(n * log(n)) comparisons" to "we need O(n * log(n)) time" you need additional assumptions, like "memory access takes O(1) time, and the speed of one comparison is independent of the total amount of data". But for any reasonable set of assumptions an algorithm that uses O(n * log(n)) comparisons takes at least O(n * log(n)) time (probably more since memory access isn't really O(1), it's just common to pretend that it is).
- webkike 7y agoI 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