HPC - Merge Sort with OpenMP tasks

The file omp-merge-sort.c contains an implementation of the recursive Merge Sort algorithm. The implementation reverts to Selection Sort when the size of the subvector to sort is less than a cutoff value; this is a standard optimization that reduces the overhead of recursive calls on small vectors.

The program generates a random permutation of the integers \(0, 1, \ldots, n-1\), and then sorts the permutation using Merge Sort. It if therefore easy to check the correctness of the result by comparing it to the sequente \(0, 1, \ldots, n-1\).

You are asked to parallelize the Merge Sort algorithm using OpenMP tasks, by creating separate task for each recursive call. Measure the execution time of the parallel version and compare it with the serial implementation. To get meaningful results, choose an input that requires at least a few seconds to be sorted using all available processor cores.

To compile:

    gcc -std=c99 -Wall -Wpedantic -fopenmp omp-merge-sort.c -o omp-merge-sort

To execute:

    ./omp-merge-sort 50000

Files

• omp-merge-sort.c