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.
Unlikely, since table variables are, like temp tables, stored in TempDB and do not require a large amount of memory (no more than temp tables do)
Instead of temporary tables you could use permanent tables and have a routine that truncates the permanent table when it is no longer needed.
Personally I would not recommend doing that, it introduces concurrency issues and permanent tables log more than temp tables, so now it's the user database and user database log growing, more than TempDB would have and without all the optimisations that TempDB has for frequent table creation.
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.
Sorts spill to TempDB just as hash tables do, and in fact are more likely to spill because of the memory grants required. Sorts are expensive operations and it's very likely that forcing a merge join instead of the hash that the optimiser chooses will result in a slower query that uses more resources.
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass