O 記法は、ある定数Cがあって、n がある程度大きいときに常に以下の式が成り立つとき

f(n) < C * g(n) ---------- (*)

f(n) = O(g(n)) と表記する。ってのが定義だから、この場合は T(n) = O(n log n) であってる。

最後端折っちゃったけど、つづき
T(n) = n log n + n * T(1)

T(1) は入力サイズにかかわらず一定なので定数 d とする。

T(n) = n log n + d * n

n がある程度大きくなれば常に d < log n なので

T(n) = n log n + d * n < n log n + n log n = 2 n log n

整理すると

T(n) < 2 n log n

O記法に戻って f(n) を T(n)、C を2、g(n) を n log n と対応させると T(n) = O(n log n)
アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。