The story so far is easy enough to understand. At one end of the spectrum of language implementations we have the pure compiler, which generates nothing but machine code and uses no run time library or package.
At the other end we have the interpreter, which generates no machine code and is all run time package in the form of a complete VM for the language.
Of course, in the real world these really are two ends of the spectrum and real compilers use different amounts of run time library, so slowly sliding towards the interpreter end of the spectrum. But what about interpreters? Do they have a way of sliding towards the compiler end of the spectrum?
An interpreter can generate some machine code to get a job done quicker if this is important. A modern VM will use all sorts of techniques to make it faster and more efficient. For example, for each instruction in the intermediate language the VM could ask which is going to be quicker: to call a routine or to generate machine code to get the job done. This approach is often called Just-In-Time or JIT compilation. It is usually explained as the VM compiling the intermediate language just before it is run, but this isn't really a good way to think of it.
The VM does compile the intermediate language, but most what it produces is just lots of calls to routines that constitute a runtime package. So the JIT is a sort of mixture of interpreting the code and compiling the code according to what makes best use of the real machine.
This is still a source of lots of arguments in the programming world - is it a compiler, an interpreter, a JIT or what?
In practice there is a lot of overlap, but it is still true that languages at the compiler end of the spectrum run faster than languages at the interpreter or VM end of the spectrum. However, the gap isn't as wide as you might think and a lot depends on how well the compiler and VM are implemented.
The merge sort is an under-appreciated algorithm - yet it is neat, clever and it still has its uses. With the rise of big data, parallel methods and online processing, you can even argue that it is gr [ ... ]