Java Sorting – Why Not Use Radix Sort on Primitives?

The question is confusing, as C and C++ are languages, while JVM is a virtual machine and .Net is a platform. Scala could be implemented in C or C++, and it could generate machine code instead of bytecode for a virtual machine.

Answering the question that was asked:

Scala was not implemented in C or C++ because Scala, the language in which it is actually implemented, is a much better language.

Why is it better? Well, go read about Odersky's goals for the Scala language.

Answering the question that may have been intended:

Scala generates primarily JVM bytecode because that provides great portability as well as features such as a reliable and efficient garbage collector, run-time optimizations and just-in-time compilation by the JVM.

Let me repeat that last thing: JVM will compile to machine code hot spots in the code it is running. That's compile just like C and C++ compilers do.

There are other virtual machines available, but Odersky, Scala's creator, was already very familiar with JVM. He intended to have CLR as an alternative, but the effort to get that going hasn't achieved success yet.

Answering the question that could/should have been asked:

Compiling to machine code doesn't provide enough benefits over compiling to JVM bytecode.

It is certainly possible to generate microbenchmarks in C or C++ that beat JVM-equivalents. It is also true that extremely optimized code in C or C++ will beat extremely optimized code in Java or Scala. The difference isn't all that great, however, for long-running program.

Note that Scala isn't a particularly good scripting language precisely because the overhead for short-running programs is too big.

However, in most cases the speed of development and ease of maintenance are more important than the speed of execution. In those cases, where people are more concerned in writing very high level code that is easily understand and change, the run-time optimizations provided by the JVM may easily beat compile-time optimizations made by C or C++ compilers, making JVM (and CLR) the target that will actually execute faster.

So, no matter whether the question was about Scala compiler being a machine code executable, or Scala programs being machine code, the potential speed gains do not, necessarily, translate into real speed gains.

And, by the way,

I'll give you a counter-example: Haskell. Haskell generates machine code, and, yet, Haskell programs fare worse on Debian's shootout than Scala's. Given that, can anyone be sure Scala programs would be faster if compiled directly to machine code?

That O(f(n)) really means in order of K*f(n), where K is some arbitrary constant. For radix sort this K happens to be quite big (at least order of number of bits in the integers sorted), on the other hand quicksort has one of the lowest K among all sorting algorithms and average complexity of n*log(n). Thus in real life scenario quicksort will be very often faster than radix sort.