What is the name the class of functions described by O(n log n)?
It's called linearithmic time, and is a special case of a more general class known as quasi linear.  As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k &gt; 1$.