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:
“I have travelled a good deal in Concord; and everywhere, in shops, and offices, and fields, the inhabitants have appeared to me to be doing penance in a thousand remarkable ways.... The twelve labors of Hercules were trifling in comparison with those which my neighbors have undertaken; for they were only twelve, and had an end; but I could never see that these men slew or captured any monster or finished any labor.”
—Henry David Thoreau (1817–1862)
“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)
“To people off alone, as we were, there is something stirring about finding evidences of human labour and care in the soil of an empty country. It comes to you as a sort of message, makes you feel differently about the ground you walk over every day.”
—Willa Cather (1873–1947)