Merge sort

Merge sort (sau sortarea prin interclasare) este un algoritm de sortare de tip divide et impera care presupune următorii pași generali:

1. se împarte șirul de N elemente de sortat în N șiruri de lungime 1
2. se aplica operația de interclasare ("merge") între câte două astfel de șiruri de lungime 1, rezultând N/2 șiruri sortate de lungime 2
3. se repetă pașii de mai sus realizând interclasări între șiruri din ce în ce mai mari, până se ajunge la un șir sortat de N elemente. Numărul de pași de interclasare necesari este log₂N, iar operațiile de interclasare de la un pas se realizează în O(N), deci complexitatea algoritmului merge sort este O(Nlog₂N).

Pentru a paraleliza acest algoritm, putem observa că operațiile de interclasare de la fiecare pas se pot realiza în paralel. Totuși, operațiile de "merge" de la fiecare pas trebuie terminate în totalitate înainte de a trece la următorul pas, deci avem nevoie de o barieră (sau un mecanism similar) după fiecare pas de interclasare. Se poate observa că gradul de paralelism de la un pas de interclasări este din ce în ce mai mic pe măsură ce avansăm în algoritm, pentru că numărul de operații de "merge" de la fiecare pas scade. Complexitatea algoritmului paralel este O(N) pentru P=N.

O reprezentare grafică a algoritmului de merge sort paralel se poate observa în imaginea de mai jos, unde operațiile cu aceeași culoare pot fi realizate în paralel, iar simbolurile cu roșu reprezintă bariere.