To be honest, I had forgotten the O(n) solution and vaguely remembered the nlogn solution. After that experience, I have both solutions lodged in my brain.

I suppose if you had to optimize for least space used sorting in place and doing it they way they suggested would be best.