Mumbai University > Computer Engineering > Sem 8 > Parallel & Distributed System

The Even - Odd bubble sort can perform sorting of n numbers with n/2 processing elements.

In 1st parts if swaps all odd numbers with mat and 2nd parts it swaps all even numbers with next.

Example :

This way n numbers can be saved in n passes.

without parallelism, bubble sort takes $0 (n^2)$

with even-odd parallelism, bubble sort takes time $0(n)$ but with n/2 processing elements.

Serial Run : $0(n^2)$

Parallel Run : $0(n)$

communication cost in parallel run is 1 element communicated by end processing element in each pass ad hence I/O communication cost is O(n)