How do you check if two algorithms return the same result for any input?

How do you check if two algorithms (say, Merge sort and Naïve sort) return the same result for any input, when the set of all inputs is infinite?

Update: Thank you Ben for describing how this is impossible to do algorithmically in the general case. Dave's answer is a great summary of both algorithmic and manual (subject to human wit and metaphor) methods that don't always work, but are quite effective.

In contrast to what the nay-sayers say, there are many effective techniques for doing this.

-
Bisimulation is one approach. See for example, Gordon's paper on Coinduction and Functional Programming.

-
Another approach is to use operational theories of program equivalence, such as the work of Pitts.

-
A third approach is to verify that both programs satisfy the same functional specification. There are thousands of papers on this approach.

-
A fourth approach is to show that one program can be rewritten into the other using sound program transformations.

Of course none of these methods is complete due undecidability, but volumes and volumes of work has been produced to address the problem.

StackExchange Computer Science Q#2059, answer score: 20