2
If such an algorithm exists, how is it possible for an algorithm to sort a data collection in linear time even if it falls in the worst possible case (reversed)?
1 answer
2
It certainly does, depending on the scenario. With the right data (even in the worst case), with sufficient resources (memory or processors in parallel, for example) it is possible yes. If it pays off, it’s another story.
But within the normalcy that is out there, the best possible would be an O(n log n).
There are algorithms that have linear complexity in the best case, which may be the case where everything is already sorted as it should. It is possible in the Quicksort under specific implementation. Insertation Sort and Bubble Sort are other known who can.
The worst case depends on the algorithm, it has case that being reversed can easily be O(n). Or even O(n/2) in some cases.
If you only work with integers of the correct size you can use the Radix Sort. There are other algorithms that do count to sort the integers (example). When the data is informative of its greatness it is possible to use it without making comparisons.
In some cases you can with the Pigeonhole Sort
Browser other questions tagged algorithm classification
You are not signed in. Login or sign up in order to post.
Yes, but it is not a comparative algorithm. It does not even make a comparison between the elements of the set. Comparative algorithms are limited to
o(n log n)worst-case– Jefferson Quesado