Comparison With Other Sort Algorithms
Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n), and is often faster in practical implementations. On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays. On the other hand, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Python uses timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm for Java SE 7, and on the Android platform.
Read more about this topic: Merge Sort
Famous quotes containing the words comparison with, comparison and/or sort:
“Intolerance respecting other people’s religion is toleration itself in comparison with intolerance respecting other people’s art.”
—Wallace Stevens (1879–1955)
“In comparison to the French Revolution, the American Revolution has come to seem a parochial and rather dull event. This, despite the fact that the American Revolution was successful—realizing the purposes of the revolutionaries and establishing a durable political regime—while the French Revolution was a resounding failure, devouring its own children and leading to an imperial despotism, followed by an eventual restoration of the monarchy.”
—Irving Kristol (b. 1920)
“It seemed there was a sort of poisoning, an auto-infection of the organisms, so Dr. Krokowski said; it was caused by the disintegration of a substance ... and the products of this disintegration operated like an intoxicant upon the nerve-centres of the spinal cord, with an effect similar to that of certain poisons, such as morphia, or cocaine.”
—Thomas Mann (1875–1955)