Skip to main content

Merge Sort

Merge sort (or merge sorting) is a divide and conquer sorting algorithm that follows these general steps:

  1. Divide the array of N elements to be sorted into N arrays of length 1.
  2. Apply the merge operation between every two such arrays of length 1, resulting in N/2 sorted arrays of length 2.
  3. Repeat the above steps by merging progressively larger arrays until a sorted array of N elements is achieved.

The number of merge steps required is log2N, and the merging operations at each step are performed in O(N) time. Therefore, the complexity of the merge sort algorithm is O(Nlog2N).

To parallelize this algorithm, we can observe that the merging operations at each step can be performed in parallel. However, the merge operations at each step must be completed entirely before moving to the next step, so we need a barrier (or a similar mechanism) after each merge step. It can be observed that the degree of parallelism decreases with each merge step as we progress through the algorithm because the number of merge operations at each step decreases. The parallel algorithm's complexity is O(N) for P=N.

A graphical representation of the parallel merge sort algorithm can be seen in the image below, where operations with the same color can be performed in parallel, and the symbols in red represent barriers.