Performance of ORDER BY

I am wanting some ideas about improving the performance of ORDER BY in
our use.  I have a DB on the order of 500,000 rows and 50 columns.
The results are always sorted with ORDER BY.  Sometimes, the users end up
with a search that matches most of the rows.  In that case, I have a
LIMIT 5000 to keep the returned results under control.  However, the
sorting seems to take 10-60 sec.  If I do the same search without the
ORDER BY, it takes about a second.

I am currently on version 8.0.1 on Windows XP using a Dell Optiplex 280
with 1Gb of ram.  I have set sort_mem=100000 set.

Any ideas?

Thanks,
Glenn