See if the queries don't need to sort all those rows. Re-writing the query to filter out certain rows could help. But I don't know what your needs are.

If you could use table variables instead of temporary tables, that could help. But it requires a large amount of memory. Upgrading memory could help.

Instead of temporary tables you could use permanent tables and have a routine that truncates the permanent table when it is no longer needed.

Some databases have the option SORT_IN_TEMPDB set to on. Maybe you need to set it to off.

If you could increase the size of tempdb by putting it on a different hard drive, that could improve performance too. For more information on optimizing tempdb see this link:

http://msdn.microsoft.com/en-us/library/ms175527%28v=sql.105%29.aspx

For capacity issues, see this link: http://msdn.microsoft.com/en-us/library/ms345368%28v=sql.105%29.aspx

P.S. For the sorting issue, look at the estimated execution plan. See if there is a hash join or merge join. If the sorts are using hash joins to sort, those can use a great deal of space in tempdb. If introducing an ORDER BY clause to the tables could happen before the main sorting, then the optimizer would use a merge join to get the final sorted result. It would be worth re-writing the joining and sorting portions of the stored procedure not just to save space in tempdb, but to save time. Merge sorts have both of these advantages. Merge sorts happen when the different tables being sorted are semi-sorted already. The optimizer chooses this underlying algorithm under certain conditions. If it does, it will save you space in your tempdb. If performance of the stored procedures is currently faster than acceptable and tempdb space is your absolute concern, you could rewrite the queries to use nested loops instead of hash joins. But this could be a considerable development effort and the stored procedure doing the sorting (and presumably joining) would take much longer than it was previously taking.