William L. Maltby wrote:
A different algorithm, or something like pre-sorting the data might make a huge difference.
That can make a huge difference. My post mentioning the order of data and keys is the "live" equivalent of exactly what Les mentions. Taken a step further (if this is what you mean Les, sorry for repeating), it may be possible to sequentially pre-read and sort (or pre-read in indexed order) and feed that to the application *if* it has the ability to take data from a sequential file or stream. *BIG* gains possible that way.
I don't think there is much in the way I can modify how the data is read in. AFIK, it's all based on time data.
Further, if you have access to the source, or have tunable parameters available (like size of each read call) and can achieve very large reads of sequential data, system overhead (context switch, ...) is greatly reduced. What does SAR show the split between user/system time being? Might be a lot to gain there too.
Sar reports 85% user, and about 9% system, with a current iowait of 0.27%, so there is not much wait to things.