Editing Merge sort (section)

==Optimizing merge sort==
[[Image:Merge sort animation2.gif|thumb|Tiled merge sort applied to an array of random integers.  The horizontal axis is the array index and the vertical axis is the integer.]]
On modern computers, [[locality of reference]] can be of paramount importance in [[software optimization]], because multilevel [[Memory hierarchy|memory hierarchies]] are used. [[Cache (computing)|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 '''{{visible anchor|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{{Example needed|date=August 2016}} on machines that benefit from cache optimization. {{Harv|LaMarca|Ladner|1997}}