Implementation of Parallel Merge Sort

Experiment No: HPC-03

TITLE: - For Merger Sort, based on existing sequential algorithms, design and implement parallel algorithm utilizing all resources available.

• Implement Any One Sorting Strategy(Merge sort Or Bubble Sort)

Problem Statement: - Understand Parallel Sorting Algorithms like Bubble sort and Merge Sort.

Objective:

• To understand the implementation of Merger sort and bubble sort
• To study OpenMP Parallel programming model

Requirements (Hw/Sw): PC, gcc, OpenMP tool, Ubuntu system,C/C++.

Theory:-

i) What is Sorting?

Sorting is a process of arranging elements in a group in a particular order, i.e., ascending order, descending order, alphabetic order, etc.

Characteristics of Sorting are:

• Arrange elements of a list into certain order

• Make data become easier to access

• Speed up other operations such as searching and merging. Many sorting algorithms with different time and space complexities

ii) What is Parallel Sorting?

• parallel sorting algorithm as compared with traditional sequential sorting algorithm which can execute a task on many processing device ,and then combined together at the end to get correct results.

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.

Design methodology:

• Based on an existing sequential sort algorithm

– Try to utilize all resources available

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

• Completely new approach

– New algorithm from scratch

– Harder to develop

– Sometimes yield better solution

Merge Sort

• Collects sorted list onto one processor

• Merges elements as they come together

• Simple tree structure

• Parallelism is limited when near the root

Merge Sort

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.
           Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. 

Theory:

To sort A[p .. r]:

1. Divide Step

If a given array A has zero or one element, simply return; it is already sorted. Otherwise, splitA[p .. r] into two subarraysA[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two subarraysA[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarraysA[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

Example:
The following diagram from shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.

Algorithm for Parallel Merge Sort:

1. Procedure parallelMergeSort

2. Begin

3. Create processors Pi where i = 1 to n

4. if i > 0 then recieve size and parent from the root

5. recieve the list, size and parent from the root

6. endif

7. midvalue= listsize/2

8. if both children is present in the tree then

9. send midvalue, first child

10. send listsize-mid,second child

11. send list, midvalue, first child

12. send list from midvalue, listsize-midvalue, second child

13. call mergelist(list,0,midvalue,list, midvalue+1,listsize,temp,0,listsize)

14. store temp in another array list2

15. else

16. call parallelMergeSort(list,0,listsize)

17. endif

18. if i >0 then

19. send list, listsize,parent

20. endif

21. end

Input :

1. Array of integer numbers.

Output :

1. Sorted array of numbers

ALGORITHM ANALYSIS

1. Time Complexity Of parallel Merge Sort and parallel Bubble sort in best case is( when all data is already in sorted form):O(n)

2. Time Complexity Of parallel Merge Sort and parallel Bubble sort in worst case is: O(n logn)

3. Time Complexity Of parallel Merge Sort and parallel Bubble sort in average case is: O(n logn)

APPLICATIONS

1. Representing Linear data structure & Sequential data organization : structure & files

2. For Sorting sequential data structure


                                           SAMPLE PROGRAM FOR OPENMP

PARALLEL MERGE SORT PROGRAM

Parallel Merge Sort Manual & Program

CONCLUSION

Thus, we have studied Parallel Bubble and Parallel Merge sort implementation.