Re: An interview question
- From: Kai-Uwe Bux <jkherciueh@xxxxxxx>
- Date: Wed, 26 Sep 2007 02:18:14 -0700
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.