0
$\begingroup$

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 :).

$\endgroup$
  • 3
    $\begingroup$ You should use the native sorting routine. $\endgroup$ – Yuval Filmus May 8 '15 at 5:57
  • $\begingroup$ @Yuval Filmus: Thanks for answering! May I have your reasoning? $\endgroup$ – user26658 May 8 '15 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$ – Yuval Filmus May 8 '15 at 19:59
  • $\begingroup$ When in doubt, benchmark. Premature optimization is the root of all evil. $\endgroup$ – jmite May 9 '15 at 4:56
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! The explanation is what I really needed. I need someone else to confirm with! $\endgroup$ – user26658 May 9 '15 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$ – jmite May 9 '15 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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