Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and Neumann as early as 1948.
Read more about Merge Sort: Algorithm, Natural Merge Sort, Analysis, Use With Tape Drives, Optimizing Merge Sort, Parallel Processing, Comparison With Other Sort Algorithms, Utility in Online Sorting
Famous quotes containing the words merge and/or sort:
“Popular art is normally decried as vulgar by the cultivated people of its time; then it loses favor with its original audience as a new generation grows up; then it begins to merge into the softer lighting of “quaint,” and cultivated people become interested in it, and finally it begins to take on the archaic dignity of the primitive.”
—Northrop Frye (b. 1912)
“A cold and searching wind drives away all contagion, and nothing can withstand it but what has a virtue in it, and accordingly, whatever we meet with in cold and bleak places, as the tops of mountains, we respect for a sort of sturdy innocence, a Puritan toughness. All things beside seem to be called in for shelter, and what stays out must be part of the original frame of the universe, and of such valor as God himself.”
—Henry David Thoreau (1817–1862)