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:
“Traditionally in American society, men have been trained for both competition and teamwork through sports, while women have been reared to merge their welfare with that of the family, with fewer opportunities for either independence or other team identifications, and fewer challenges to direct competition. In effect, women have been circumscribed within that unit where the benefit of one is most easily believed to be the benefit of all.”
—Mary Catherine Bateson (b. 1939)
“There are people who indulge themselves in a sort of lying, which they reckon innocent, and which in one sense is so; for it hurts nobody but themselves. This sort of lying is the spurious offspring of vanity, begotten upon folly.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)