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:
“We don’t know when our name came into being or how some distant ancestor acquired it. We don’t understand our name at all, we don’t know its history and yet we bear it with exalted fidelity, we merge with it, we like it, we are ridiculously proud of it as if we had thought it up ourselves in a moment of brilliant inspiration.”
—Milan Kundera (b. 1929)
“Alice felt dreadfully puzzled. The Hatter’s remark seemed to her to have no sort of meaning in it, and yet it was certainly English. “I don’t quite understand you,” she said, as politely as she could.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)