There can't exist a sorting the runs in a linear time, because you need to make comparisons whether directly like merge sort, quick sort, bubble sort, ... etc or indirectly like radix sort.

how can you sort items when you don't compare them to their surroundings? and if you compare how can the complexity of such algorithm be linear?!

Radix Sort is linear only because it is non-comparative, and Counting Sort takes expected linear time if you use a hashtable (it's not guaranteed linear, it's just linear with high probability).

In general, you cannot do better than if you're using a comparative sorting algorithm. If you have a well-defined ordering on some objects, then you can sort them in assuming you can compare them in O(1).

If you take advantage of some underlying structure within those objects, then yes, you could sort faster than . That's where Radix Sort comes from. It solves the problem of sorting integers specifically, not the problem of sorting objects with an ordering.

It's less effort to just use std::sort and be okay with a factor. It's not wrong to use Radix Sort for integers, it's just that in a contest, there's a tradeoff between how well it would benefit your solution, and the time you need to implement it (also, the maintenance cost, and the probability that your implementation has a bug play a role).

Radix sort isn't really linear though, but rather where M is the largest number, which isn't that much better/different in theory from since we often have M > N.

(In practice we can make radix sort quite efficient though by processing x-bit chunks at the time.)