An implementation of merge-sorting for arrays that uses insertion sorting for small sub-arrays is shown below (see e.g. [33]). Here, we assume that a sufficiently large temporary integer array tmp is is available to support the merge step:
Again, because the recursive method invocations can be done in parallel, the method of this paper can be used to exploit implicit parallelism in arrayMergesort(). In figure 26, we show execution time of the serial and parallel version applied to the same random integer arrays used earlier. Although, in contrast with the previous sorting method, the method invocation trees are always well-balanced (independent of the actual values of the elements), the overhead of data movement has a clear impact on the performance of this sorting method.
Figure 26: Merge/Insertion Sorting of Random Integer Arrays