# CS3354 – Assignment 6 solved

\$35.00

## Description

Rate this product

Goal:
The goal of this assignment is to help students understand the concepts of Java
Description:
The attached source code shows an example of a program that can sort a set of
numbers using the top-down MergeSort1 algorithm. In the given implementation,
the program uses a single thread to sort the whole input. MergeSort is a sorting
algorithm that can be easily parallelized due its divide-and-conquer nature2. On
CPUs with multiple cores, multiple threads can speed up the sorting time, by
splitting the work.
MergeSort 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.
The figure below shows how an array of size 7 is split into two halves and it
continues like that until each subarray is of size one, at which point it starts
merging.
1 https://en.wikipedia.org/wiki/Merge_sort
2 https://en.wikipedia.org/wiki/Merge_sort#Parallel_merge_sort
The following is a pseudocode of the MergeSort algorithm:
mergeSort(arr[], l, r)
if r > l
Find the middle point to divide the array into two halves:
middle m = (l+r)/2
Call mergeSort for first half:
Call mergeSort(arr, l, m)
Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
The psedocode above can be modified to allow mergeSort(arr, l, m) and
mergeSort(arr, m+1, r) to run in parallel.
parallelMergeSort(arr[], l, r)
if r > l
2000 elements => 6 ms
4000 elements => 13 ms
8000 elements => 26 ms
16000 elements => 5 ms
32000 elements => 10 ms
64000 elements => 14 ms
128000 elements => 23 ms
256000 elements => 50 ms
512000 elements => 107 ms
1024000 elements => 245 ms
2048000 elements => 541 ms
4096000 elements => 1243 ms
8192000 elements => 2848 ms
16384000 elements => 6425 ms
1000 elements => 1 ms
2000 elements => 1 ms
4000 elements => 1 ms
8000 elements => 2 ms
16000 elements => 4 ms
32000 elements => 6 ms
64000 elements => 7 ms
128000 elements => 16 ms
256000 elements => 41 ms
512000 elements => 105 ms
1024000 elements => 155 ms
2048000 elements => 360 ms
4096000 elements => 803 ms
8192000 elements => 1647 ms
16384000 elements => 3474 ms
1000 elements => 1 ms
2000 elements => 1 ms
4000 elements => 1 ms
8000 elements => 1 ms
16000 elements => 3 ms
32000 elements => 6 ms
64000 elements => 66 ms
128000 elements => 12 ms
256000 elements => 33 ms
512000 elements => 54 ms
1024000 elements => 131 ms
2048000 elements => 270 ms
4096000 elements => 690 ms
8192000 elements => 1119 ms
16384000 elements => 3014 ms
1000 elements => 1 ms
2000 elements => 1 ms
4000 elements => 64 ms
8000 elements => 1 ms
16000 elements => 2 ms
32000 elements => 3 ms
64000 elements => 7 ms
128000 elements => 18 ms
256000 elements => 22 ms
512000 elements => 43 ms
1024000 elements => 104 ms
2048000 elements => 250 ms
4096000 elements => 537 ms
8192000 elements => 1054 ms
16384000 elements => 2115 ms