An algorithm is O(n log n) if it processes all elements and does logarithmic work per element. Merge sort and heap sort have this complexity.
This is faster than O(n²) but slower than O(n). For sorting, O(n log n) is optimal for comparison-based algorithms.
Multiplying n by log n gives a growth rate between linear and quadratic.