Got the same problem and found a convenient solution - at least for my tasks.

If you always have the same `ORDER BY` eg `popularity` or whatever and don't do frequent updates, eg if it's enough on a daily basis, an idea is to set up a cronjob which resorts the table every night.

    ALTER TABLE my_table ORDER BY my_sort_column ASC/DESC

This way you get the sorted results without filesort and any `ORDER BY` clause in the query. For my taks it took down query time from about 0.5-0.9 sec to ~0.004 for certain queries. The nightly ALTER query takes about 5-7sec on a 250k table and 11 year old Dell server.