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:
“In everyone’s youthful dreams, philosophy is still vaguely but inseparably, and with singular truth, associated with the East, nor do after years discover its local habitation in the Western world. In comparison with the philosophers of the East, we may say that modern Europe has yet given birth to none.”
—Henry David Thoreau (1817–1862)
“The comparison between Coleridge and Johnson is obvious in so far as each held sway chiefly by the power of his tongue. The difference between their methods is so marked that it is tempting, but also unnecessary, to judge one to be inferior to the other. Johnson was robust, combative, and concrete; Coleridge was the opposite. The contrast was perhaps in his mind when he said of Johnson: “his bow-wow manner must have had a good deal to do with the effect produced.””
—Virginia Woolf (1882–1941)
“The innocence of those who grind the faces of the poor, but refrain from pinching the bottoms of their neighbour’s wives! The innocence of Ford, the innocence of Rockefeller! The nineteenth century was the Age of Innocence—that sort of innocence. With the result that we’re now almost ready to say that a man is seldom more innocently employed than when making love.”
—Aldous Huxley (1894–1963)