More algorithms and surprises

Testing the intersection problem using a HashMap turned up some more interesting numbers. In spite of that being an O(m+n) algorithm (m to build the hash map, n to check for intersection) like the linear probing, it was still significantly faster than the linear probing, even with the time to sort the two arrays removed. The HashMap based intersection did have the disadvantage of taking about an extra 3% memory.

Another surprise came from the fact that sorting the two arrays was just a very minor part of the runtime for the linear intersection, even though it should be m*log(m) + n*log(n), as opposed to the intersection's m+n time. I suspect, though I'm not certain, that that is due to locality and caching, since the sort operates on one array at a time, so the processor is better able to pre-fetch the needed data. Either that or Josh Bloch, Neil Gafter & John Rose have magical programming powers, which I'm also not ready to rule out quite yet.