HPC - Merge Sort with OpenMP tasks

Moreno Marzolla

Last updated: 2023-10-24

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

The program generates and sorts a random permutation of \(0, 1, \ldots, n-1\); it if therefore easy to check the correctness of the result, since it must be the sequente \(0, 1, \ldots, n-1\).

The goal is to parallelize the Merge Sort algorithm using OpenMP tasks. You might want to proceed as follows:

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