Parallel Algorithm Sorting - Parallel Algorithm

How sorting is done in parallel algorithm?

The process by which the elements in a group are arranged in a particular order in known as Sorting. The order may be ascending order, descending order, alphabetic order etc. Different types of sorting are:

• Enumeration Sort
• Odd-Even Transposition Sort
• Parallel Merge Sort
• Hyper Quick Sort

A sequential sorting algorithm is not that efficient for sorting huge volume of data. Hence parallel algorithms are used in sorting.

Enumeration Sort

All the elements are arranged in a list by identifying the final position of each element of the sorted list. Each element is compared with other elements and the number of elements having smaller values is compared.

For instance, for any two elements, ai and aj, any one of the case may be true.

• ai < aj
• ai > aj
• ai = aj

Algorithm

Odd-Even Transposition Sort

Under this method of sorting, two adjacent numbers are compared and if the first number is greater than the second number, the two numbers are swapped to get an ascending order list. For descending order list applies vice-versa. This method of sorting operates in two phases - odd phase and even phase. In both the phases, numbers are exchanged with the adjacent numbers in the right by the processes.

Algorithm

Parallel Merge Sort

The unsorted list is divided into smallest possible sub-lists by Merge sort. Then it is compared with the adjacent list and merged in sorted order. By following divide and conquer algorithm, parallelism is implemented.

Algorithm

Hyper Quick Sort

Under this sorting, the quick sort is implemented on hypercube. The steps of sorting are:

• The unsorted list is divided among each node.
• Each node is sorted locally.
• The median value is broadcasted from node 0.
• Each list is locally divided and the halves are exchanged across the highest dimension.
• 3 and 4 steps are repeated in parallel until the dimension reaches 0.

Algorithm