So did you measure how much of the speed improvement came from your careful memory copying tuning and how much came from the algorithmic change?
EDIT: fixed my math, thank you andruby
Yes, N^2 to NlogN feels like it should be a bigger factor, but remember that constants in front of this matter. You are replacing 2-level nested but very straightforward loops that rip through cached memory at blazing speed without any disruption to CPU pipelines with a single loop that involves quite a bit of condition checking and array element swaps (cache is busted, pipelines are busted - conditions are very hard to predict). You gain some, you lose some.
It would be interesting to see them applied separately. The commenters claim that both are important has not been shown by his example yet.
However the results are impressive. Great job with the solution.