The OS scheduler still does the comparisons (and sorting). How otherwise would the threads wake up in order if they weren't sorted by somebody?

Just because a sorting algorithm doesn't use any comparisons doesn't make it O(0).

For example Radix Sort (http://en.wikipedia.org/wiki/Radix_sort) is not a comparison based sort and its complexity is O(k.n) where k is the max size of elements.