If such an algorithm exists, how is it possible for an algorithm to sort a collection of linear time data even if it falls in the worst case (inverted)?
If such an algorithm exists, how is it possible for an algorithm to sort a collection of linear time data even if it falls in the worst case (inverted)?
Certainly it exists, it depends on the scenario. With the right data (even in the worst case), with enough resources (memory or processors in parallel, for example) is possible. It pays off is another story.
But within the normality that is out there, the best possible would be an O (N * logN).
There are algorithms that have linear complexity in the best case, which may be the case where everything is already classified as it should. It is possible in Quicksort in specific implementation. Insertation sort and Bubble sort are other acquaintances who can.
The worst case depends on the algorithm, it has to be reversed, it can easily be O (N). Or even O (N / 2) in some cases.
Working with only the right-sized integer can use 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 do with Pigeonhole sort