Is it better to use comparison or radix sort to sort a long sequences of java int array?

I know that I should probably use mergesort (NlogN) for comparison sort, since it is one of the fastest and compare that to LSD or MSD. I thought about how for extremely large N, the logarithm would be larger than runtime for LSD, but other than that, the mergesort (comparison) is better.

I wonder if my reasoning is correct because I have seen a question asking about Strings and the answer was the aforementioned. Now this question is about long sequences of java int array and I wonder if I am missing the point.

Any help is appreciated :).

  • 3
    $\begingroup$ You should use the native sorting routine. $\endgroup$ May 8, 2015 at 5:57
  • $\begingroup$ @Yuval Filmus: Thanks for answering! May I have your reasoning? $\endgroup$
    – user26658
    May 8, 2015 at 16:45
  • $\begingroup$ The native sorting routine is usually optimized, and so would probably be faster than any naive implementation of whatever sorting algorithm. In the case of Java, it might be (though I doubt it) that it is implemented in native code rather than bytecode. $\endgroup$ May 8, 2015 at 19:59
  • $\begingroup$ When in doubt, benchmark. Premature optimization is the root of all evil. $\endgroup$ May 9, 2015 at 4:56

1 Answer 1


In theory sorting a long sequence of int should be a prime candidate for radix sort as it grows linear in the number of elements to be sorted, while any comparison based sorting algorithm can't be faster than N log N.

  • $\begingroup$ Thanks! The explanation is what I really needed. I need someone else to confirm with! $\endgroup$
    – user26658
    May 9, 2015 at 4:01
  • $\begingroup$ Note that this will be better in the Big-O sense, but it's possible that a Quicksort or Mergesort will be faster in practice due to smaller constants. The only way to know is to test. $\endgroup$ May 9, 2015 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.