Andy gave some good hints, here are a few additions:

1. Yes, of course correct code is the most important. The question is the border cases, sometimes the code is mostly correct, but fixing border cases makes then slower. One idea here is to have a general fully correct procedure and then sub methods that well work for particular cases. I my opinion, the default code should always be the fully correct one.
2. Timing vs. AbsoluteTiming: Here is another example of a shortcoming of Timing. You might want to look at the Workbench profiler.
3. Concerning cache and memory, I find $HistoryLength=0 and also MaxMemoryUsed[] very valuable.

Andy gave some good hints, here are a few additions:

1. Yes, of course correct code is the most important. The question is the border cases, sometimes the code is mostly correct, but fixing border cases makes then slower. One idea here is to have a general fully correct procedure and then sub methods that well work for particular cases. I my opinion, the default code should always be the fully correct one.
2. Timing vs. AbsoluteTiming: Here is another example of a shortcoming of Timing. You might want to look at the Workbench profiler.
3. Concerning cache and memory, I find $HistoryLength=0 and also MaxMemoryUsed[] very valuable.