[eptcyka]

Constant time.

[WakoMan12]

O(nlogn)

[eptcyka]

Yes, but it ensures that for all inputs of a given size, runtime will be the same.

[consp]

That would more likely be a tight bound, not an upper bound.