Represent polynomial time complexity as linearythmic
You cannot "demonstrate" that a running time is $\Theta(n\log n)$ experimentally. All you can do is give evidence. Such evidence would be a constant $C$ such that for large $n$, $Cn\log n$ is a good approximation to the empirical running time.

You found the best polynomial approximation to your input. Since $Cn\log n$ is not a polynomial, this kind of approach cannot possibly give you the answer $Cn\log n$. If you want $Cn\log n$ to be a possible answer, you need to include such functions in the family of functions you are optimizing over.

Finally, to demonstrate that $Cn\log n$ is a better approximation that your polynomial approximation or a linear approximation, all you have to do is to compare the error in the approximation $Cn\log n$ to the errors in the other two options. Smallest error wins.