Re: An interview question

xhli wrote:

Hi, all, I have an interview question I don't know:

The interviewer said that in C++ std lib, sorting algorithm is quick sort
by default, while in Java, the default one is merge sort. Why there are
difference? And what is the benefits?

Does any one have any ideas?

a) In C++, the standard library provides std::sort(), std::stable_sort<> and
std::qsort() for backward compatibility. The standard does not specify the
implementation for any of these (the function name "qsort" may be taken as
a hint toward a permissible implementation, but it is by no means required
to be quicksort).

Implementations descending from the HP/SGI reference implementation often
implement std::sort() as introsort to avoid the quadratic worst case
runtime of quick sort.

b) With regard to Java prefering merge sort (although the interviewer might
be mistaken in that regard, too), I would first check how arrays (or
sequences in general) are implemented in Java. Maybe, the sequence data
structures in Java make merge sort the better choice.

Another thing to note isthat the incredible speed of quicksort is not due to
a smaller number of required comparisons but due to a smaller number of
swap operations. Since Java has reference semantics, swaps are probably
just done on pointers and therefore cheap. The benefit of quicksort might
be marginal in that setting.


Kai-Uwe Bux

Relevant Pages

  • Re: e-commerce portal
    ... haven't had a single site that sees a need for this sort of hardening. ... Java anymore. ... PHP is a technology that has gotten a harsh rap due to large security ... Marketing at its worse, eh? ...
  • Re: Parallel quicksort
    ... The sort method takes an extra argument numThreads saying how many ... Java folks to implement. ... But I've had a lot of fun writing different multithreaded ...
  • Re: e-commerce portal
    ... because I've never really been able to purposely hit it. ... pool licenses sitting in the background and at the most I've seen 18 ... haven't had a single site that sees a need for this sort of hardening. ... About Java, it's really a shame that by the time RD finally came out ...
  • Re: SortedMap question?
    ... worse than quick sort. ... quicksort has Oworst-case time. ... asymptotically superior in Java for bytes, shorts, and chars, too (256 ... or 64K integer arrays are not onerous in memory usage in modern computers). ...
  • Re: Sorting the Arrays
    ... just by advising how to invoke the charSortArray ... Im a new to java, so Im trying to learn, but I need help on some part, Im ... I've look at ways to sort arrays on the net but I ddin't get any ... >> at the point where I have to sort the Array ...