Pratik,
You will probably have to experiment with this as there are so many variables and some of them a host specific.
Try the TAGSORT option; that can sometimes speed up a sort by reducing disk I/O.
Unless you have text with lots of white-space, the compress=yes can actually slow down SAS.
z/OS installations often use non-SAS sort tools (we used SyncSort years ago). You may be able to speed it up by passing parameters directly to the tool. Check SAS's z/OS companion.
Another possibility is to use PROC SQL. I don't know that it would speed it up, but do know that it uses different SAS routines.
Doc Muhlbaier
Duke