Editing Merge sort (section)

==== Practical adaption and application ====
The multiway merge sort algorithm is very scalable through its high parallelization capability, which allows the use of many processors. This makes the algorithm a viable candidate for sorting large amounts of data, such as those processed in [[computer cluster]]s. Also, since in such systems memory is usually not a limiting resource, the disadvantage of space complexity of merge sort is negligible. However, other factors become important in such systems, which are not taken into account when modelling on a [[Parallel random-access machine|PRAM]]. Here, the following aspects need to be considered: [[Memory hierarchy]], when the data does not fit into the processors cache, or the communication overhead of exchanging data between processors, which could become a bottleneck when the data can no longer be accessed via the shared memory.

[[Peter Sanders (computer scientist)|Sanders]] et al. have presented in their paper a [[bulk synchronous parallel]] algorithm for multilevel multiway mergesort, which divides <math>p</math> processors into <math>r</math> groups of size <math>p'</math>. All processors sort locally first. Unlike single level multiway mergesort, these sequences are then partitioned into <math>r</math> parts and assigned to the appropriate processor groups. These steps are repeated recursively in those groups. This reduces communication and especially avoids problems with many small messages. The hierarchical structure of the underlying real network can be used to define the processor groups (e.g. [[19-inch rack|racks]], [[Computer cluster|clusters]],...).<ref name=":0" />