Merge Sort Performance As we have seen, Merge Sort is O(n ·
log(n)). Despite requiring extra storage, Merge Sort has a
number of advantages: - 39% fewer comparisons than Quicksort -
Merge Sort is inherently sequential: - has good memory locality
and cache performance - can be done with off-line media such as
disk - can be parallelized easily: parts of the input array can
be sorted independently by separate computers. - can efficiently
merge in updates to an existing sorted array - If the highest
element in the low sublist is less than the lowest element in
the high sublist, the merge can be omitted.