This is an oversimplification. Some compute intensive parts can get significant speed ups through careful use of data parallelism (such as SIMD). Others needs parallelism at the thread level. Etc. Optimizing for memory patterns is important as is trying to keep the working set within a near-level cache.

Cache locality will never beat algorithmic complexity as a performance factor. Don't exaggerate its importance.

It can, when the constant portion of the algorithm chosen is high and the number of items being pushed through the algorithm is low.

e.g. bubblesort will beat quicksort for tiny lists or large lists which are already sorted.

Or, put another way, 1000 operations against 1ns latency memory (L1) has the same performance as 10 operations against 100ns latency memory (RAM).