MINI PROJECT

Title:
Implement merge sort and multithreaded merge sort. Compare time required by
both the algorithms. Also analyze the performance of each algorithm for the
best case and the worst case.

Objective:
Compare time required and analyse performance of each algorithm for the best
case and the worst case.

Prerequisite:
a) Basic of Java Programming
b) Concept of sorting algorithms and time complexity
Theory:
Merge Sort:
Merge sort is a highly effective sorting algorithm that follows the divide-and-
conquer approach. The method involves recursively dividing an unsorted list
into smaller sub-lists, each with one element, and then progressively merging
these sub-lists to create sorted sub-lists. One notable feature of merge sort is its
stability, meaning it preserves the relative order of equal elements during the
sorting process. The time complexity of merge sort is (O(n log n)), making it a
preferred choice for large datasets. However, it comes with a space complexity
of (O(n)) due to the additional space required for the merging process.
Multithreaded Sorting:
Multithreaded sorting algorithms aim to enhance sorting performance by
capitalizing on parallelism. In this approach, the sorting task is divided among
multiple threads that can execute concurrently. Efficient coordination and
synchronization between threads are critical to ensuring the correct sorting of
data. Load balancing becomes a key consideration to distribute work evenly
among threads, preventing idle times or overloading. Multithreaded sorting is
particularly advantageous in systems with multiple processors or cores, where it
can significantly improve scalability. However, challenges such as
synchronization, race conditions, and deadlocks must be carefully addressed in
the implementation to achieve optimal results.
Performance Comparison:

a): Standard Merge Sort (Single-Threaded):

Best Case: O(n log n)

Worst Case: O(n log n)
Average Case: O(n log n)

b): Simplified Multithreaded Merge Sort:

Best Case: O(n log n)

Worst Case: O(n log n)
Average Case: O(n log n)

> In terms of time complexity, both standard merge sort and multithreaded
merge sort have the same time complexity for best, worst, and average cases.

> The performance analysis for both algorithms is the same because they both
have the same time complexity. In the best and worst cases, they exhibit O(n log
n) time complexity.

> However, the multithreaded merge sort can potentially take advantage of
multiple CPU cores on a multi-core machine, providing better performance for
large input arrays due to parallelism. This can be especially useful when sorting
very large datasets.

> In summary, the multithreaded merge sort is a parallel version of the standard
merge sort and can provide improved performance for large datasets on multi-
core processors.

> However, the multithreaded version may provide a performance improvement

on multi-core processors for large arrays.

> It can take advantage of parallelism to sort the array faster, but there is an
overhead associated with creating and managing threads, so for small arrays, it
might be slower than the standard merge sort.
 MERGE -SORT
// ------------------------------------------------------------------------------
// Merge Sort
// ------------------------------------------------------------------------------

public class MergeSort {

public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int[] leftArray = new int[n1];

int[] rightArray = new int[n2];

for (int i = 0; i < n1; i++)

leftArray[i] = arr[left + i];
for (int i = 0; i < n2; i++)
rightArray[i] = arr[mid + 1 + i];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = leftArray[i];
i++;
k++;
}

while (j < n2) {

arr[k] = rightArray[j];
j++;
k++;
}
}

public static void mergeSort(int[] arr, int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);
 merge(arr, left, mid, right);
}
}

public static void main(String[] args) {

int[] arr = {29,13,20,9,3,47,18};

System.out.println("----------------------------------------------");

System.out.println("Unsorted Array :");

for (int value : arr) {
System.out.print(value + " ");
}

mergeSort(arr, 0, arr.length - 1);

System.out.println();
System.out.print("----------------------------------------------");

System.out.println("\nSorted Array:");
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
System.out.println("----------------------------------------------");
}
}
OUTPUT:

MULTITHREADED MERGE -SORT

// ---------------------------------------------------------------------------
// Multithreaded Merge Sort
// ---------------------------------------------------------------------------
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class MultithreadedMergeSort {

public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int[] leftArray = new int[n1];

int[] rightArray = new int[n2];

for (int i = 0; i < n1; i++)

leftArray[i] = arr[left + i];
for (int i = 0; i < n2; i++)
rightArray[i] = arr[mid + 1 + i];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = leftArray[i];
i++;
k++;
}

while (j < n2) {

arr[k] = rightArray[j];
j++;
k++;
}
}

public static class MergeSortTask extends RecursiveAction {

private int[] arr;
private int left;
private int right;

public MergeSortTask(int[] arr, int left, int right) {

this.arr = arr;
this.left = left;
this.right = right;
 }

@Override
protected void compute() {
if (left < right) {
int mid = left + (right - left) / 2;
MergeSortTask leftTask = new MergeSortTask(arr, left, mid);
MergeSortTask rightTask = new MergeSortTask(arr, mid + 1, right);

leftTask.fork(); // Execute the left task asynchronously

rightTask.fork(); // Execute the right task asynchronously

leftTask.join(); // Wait for the completion of the left task

rightTask.join(); // Wait for the completion of the right task

merge(arr, left, mid, right); // Merge the two sorted subarrays

}
}
}

public static void parallelMergeSort(int[] arr) {

ForkJoinPool pool = new ForkJoinPool();
pool.invoke(new MergeSortTask(arr, 0, arr.length - 1));
}

public static void main(String[] args) {

int[] arr = {23,47,9,3,17,36,12};

System.out.println("----------------------------------------------");
System.out.println("Unsorted Array:");
for (int value : arr) {
System.out.print(value + " ");
}

parallelMergeSort(arr);

System.out.println();
System.out.print("----------------------------------------------");
System.out.println("\nSorted Array:");
for (int value : arr) {
System.out.print(value + " ");
}

System.out.println();
System.out.println("----------------------------------------------");
}
}

OUTPUT: