The top-voted answer mentions that the example O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not?

I sort of view lazily-evaluated data structures (like generator expressions) as not data structures at all, but rather control flow constructs[1]. They control when, how, and if expressions are evaluated and results are returned. As a result, I feel that using lazy equivalents for your data structures qualifies as an algorithmic change. In fact, one could manually code lazy data access in an eager language, and the resulting algorithm would look very different from the original.

On the other hand, the laziness is enabled by the purity of the algorithm, so... well, it depends on your perspective. You could say that laziness makes the functional equivalent just as fast, or you could say that the functional equivalent is slower, but there's a different functional algorithm that is just as fast.

[1] Except they're still data structures. They're like, a quantum superposition of data structure and control-flow operator. Which one it is depends on how you look at it.