Depends on what you mean by "time". Going by algorithmic complexity time it's at least linear yes. Going by wall clock time (the more important one for interview code) it's constant time.
Not to mention for the OS to handle N threads would likely take some kind of non-linear time, at least N^2 if I had to take a shot in the dark. But I imagine it'd depend on the OS and how the hardware handles interrupts. Even if the thread is sleeping it still takes resources to schedule it
[1] https://en.wikipedia.org/wiki/Completely_Fair_Scheduler#Algo...
An algorithm that takes N inputs, does N operations, and then sleeps for 10 seconds is not constant time, because in the asymptotic case the N iterations will take longer than the sleep.
Sorting [5, 50] is faster wall time then [6, 60].
is just as fast as
[9]
If you really want to make it strictly constant time, just append INT32_MAX to the end of the array before sorting, and then pop it after.
A subproblem also considers the elements to be integers, then they become another "value" domain. (But in general, sorting problems only need their elements to be comparable, not necessarily integers.)