what is your sort memory buffer size set to in cognos config? how much data are you bringing back? You might try to bump up the sort buffer a little bit depending on how much memory you have, how heavily the box is used, but be careful with this.
also, there are many things there could be going on. its not easy to say what is wrong with just what you described.