Question

1. In reference to parallel sorting, what are the definitions of “sorted”. Make sure to specify both definitions. – 6 points.

Answer 1

What is parallel sorting?

Sorting is a process of arranging elements in a group in a particular order, i.e., ascending order, descending order, alphabetic order, etc. Here we will discuss about the Parallel Merge Sort.

Sorting a list of elements is a very common operation. A sequential sorting algorithm may not be efficient enough when we have to sort a huge volume of data. Therefore, parallel algorithms are used in sorting.

Parallel Sorting Algorithms explains how to use parallel algorithms to sort a sequence of items on a variety of parallel computers/processors.

Merge sort first divides the unsorted list into smallest possible sub-lists, compares it with the adjacent list, and merges it in a sorted order. It implements parallelism very nicely by following the divide and conquer algorithm.

parallel merge sort implementation:

1. recursively sort two halves of array in parallel.

2. Sequentially merge the two array helves by copying into temporary array.

3. Copy the temporary array back to original array.

The method takes two argument, array and a meximum depth.

Why paralle sorting is better:

1.•Based on an existing sequential sort algorithm

a. – Try to utilize all resources available

b. – Possible to turn a poor sequential algorithm into a reasonable parallel algorithm (bubble sort and parallel bubble sort)

Algo to sort by parallel merge sorting

What is "sorted" in parallel sorting:

"Sorted" is a shared flag. The Shared flag, sorted, initialized to true at beginning of each iteration (2 phases), if any processor perform swap, sorted = false.

Thanks