shan i am thinking in another way.
you said that it is working fine now and fetching upto 3400 records. and then you mentioned that you need to sort the records accoring to departments, because you are manipulating records according to the department on your front-end UI. So, why not manipulate the records according to the departments at the back-end as well.
I think
you should query just the records of the requested department and then use standard paging. it will save you in the future when there would be 100,000's of record.
what you people say?