Comment by 9721IsTheNumber

The sub O(n log n) significance is not in its practical "optimality". But rather that the previous lower bound was assumed to be true "by symmetry" and that result challenges some of our strongest intuitions and expectations about mathematical results. I still find this result very unsettling and a part of me remotely expects/wishes that there is some mistake somewhere.