Sort in Java
I read through the documentation and didn’t find an explanation (google without result) why the merging method was chosen to implement sorting (do they write modified, but what exactly is modified?), And not Qsort?
Is it only due to the stability of the merge algorithm or some features of working with memory in the JVM implementation that determine this choice?
After all, Qsort requires significantly less additional memory and in terms of speed (with a reasonable implementation) it almost always surpasses (if you believe Knut) MergeSort.
What are your thoughts on this?
There are no more answers, the discussion is over. Thanks a lot, everyone.
Looking at the MergeSort materials in the Wiki led me to try to implement it (despite the warning in Wiki about the great complexity of the algorithm) without allocating additional memory of size O (n).
yozh, one implementation (or a minimum of implementations) it occurred to me too. I would like to know if this is really so.
Nikolay Artamonov, and what other stable n * log (n) complexity are there? I don’t recall right away.
Then there’s another question, why didn’t they allow us to choose from several (stable / unstable)? I mean the presence of several algorithms in standard packages. It is possible that there would be less confusion. And so in Java, a huge number of method classes.
1) Thanks for the link, I will look (this is a comment with a link to http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms )
2) I found there an interesting link for implementation in jdk7 – http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 They promise remarkable characteristics (with additional memory max n / 2!) And are generally interesting.
A randomized QSort always works for O (n log n). This has a very rigorous proof.
And in Java, QSort is implemented as a sorting (with a slight modification: not one but two support elements are selected, and the array is divided into three parts). Here is an example: http://download.oracle.com/javase/1.4.2/docs/api/java/util/Arrays.html#sort (byte )