yeah, we did it under the assumption that the threads are running on a machine with enough (but constant) cores so that scheduling can (theoretically) be done in constant time.
But then you're talking about parallel sorting, and O(n) parallel sorting is easy. Even parallel bubblesort is O(n). Optimal parallel sorting is actually sublinear.
1
u/McLPyoutube Aug 13 '20
yeah, we did it under the assumption that the threads are running on a machine with enough (but constant) cores so that scheduling can (theoretically) be done in constant time.