MySQL profile on query "Creating Sort Index" using 75% of the total time
We had similar problem for huge queries. Often queries ran for hours (upto 7-8) depending upon the load on DB for 400M rows. However, our goal was to achieve group results, such as select col1, col2, col3, count(1), count(distinct col4) from table group by 1,2,3.

Underlying problem is same as yours though, as in both case DB sorts(orders) the results internally.


How creating sort index work.
On mysql website it says "The thread is processing a SELECT that is resolved using an internal temporary table." Per my algorithm understanding, system is most likely splitting data into chunks, read from disk this chunks one by one,  sorting individual chunks, putting back into some temporary disk space and so on. System does this for all chunks and eventually performs merge sort. This involves extensive read/writes.


A possible solution can be to increase your memory for DB (so that it can create bigger chunks that can stay in memory) or if you have a bigger memory somewhere else, you can program the solution by streaming from DB. This can be achieved in nlogn time. 

Programmatically, I could reduce time from on an average of 2 hrs to a consistent 7.5 minutes.