README.md

# MergeSort benchmark

## Description
Merge Sort is a recursive sorting algorithm based on comparisions. 


## Versions
We have several implementations of this benchmark:

* **01.mergesort_seq:** sequential version of this benchmark.

* **02.mergesort_outline_task:** Parallel version of the benchmark using the *task* construct on functions and the *taskwait* construct to synchronize between tasks.

* **03.mergesort_inline_task:** Parallel version of the benchmark using the *task* construct on code statements and the *taskwait* construct to synchronize between tasks. 

* **04.mergesort_outline_task_dep:** Parallel version of the benchmark using the *task* construct on functions and fine-grained dependences to synchronize between tasks.

* **05.mergesort_task_loop_dep:** Version based on the previous one that also parallelize the copy of temporary arrays with a *task loop*.

* **06.mergesort_task_loop_wait:** Version based on the previous one but uses the *wait* clause to wait for the *task loop*.

## Execution instructions

    ./mergesort N BLOCK_SIZE

where:

1. N is the number of elements to be sorted. Mandatory for all versions of this benchmark.

2. BLOCK_SIZE is used to determine the threshold when the task become *final*. If the array size is less or equal than BLOCK_SIZE, the *task* will become final, so no more task will be created inside it. Mandatory for all versions of this benchmark.

## References
https://en.wikipedia.org/wiki/Merge_sort