Optimizing Merge Sort
On modern computers, locality of reference can be of paramount importance in software optimization, because multilevel memory hierarchies are used. Cache-aware versions of the merge sort algorithm, whose operations have been specifically chosen to minimize the movement of pages in and out of a machine's memory cache, have been proposed. For example, the tiled merge sort algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a CPU's cache. Each of these subarrays is sorted with an in-place sorting algorithm such as insertion sort, to discourage memory swaps, and normal merge sort is then completed in the standard recursive fashion. This algorithm has demonstrated better performance on machines that benefit from cache optimization. (LaMarca & Ladner 1997)
Kronrod (1969) suggested an alternative version of merge sort that uses constant additional space. This algorithm was later refined. (Katajainen, Pasanen & Teuhola 1996).
Also, many applications of external sorting use a form of merge sorting where the input get split up to a higher number of sublists, ideally to a number for which merging them still makes the currently processed set of pages fit into main memory.
Read more about this topic: Merge Sort
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)
“It’s not a field, I think, for people who need to have success every day: if you can’t live with a nightly sort of disaster, you should get out. I wouldn’t describe myself as lacking in confidence, but I would just say that ... the ghosts you chase you never catch.”
—John Malkovich (b. 1953)