Merge Sort using Multi-threading in Java

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer approach. It divides the input array into smaller subarrays, recursively sorts them, and then merges them back together to obtain a sorted array. Multi-threading can be used to parallelize the sorting and merging steps, thereby potentially improving the performance of Merge Sort. Here's an explanation of how to implement Merge Sort using multi-threading in Java:

1. Divide Step: In this step, we divide the input array into smaller subarrays until we reach a base case where the subarray size is 1 or less. Each subarray will be processed by a separate thread. The division can be done recursively.
2. Sort Step: In this step, each subarray is sorted independently by a separate thread. This can be achieved by recursively calling the sorting algorithm on each subarray until the base case is reached. The sorting can be done using any sequential sorting algorithm such as Merge Sort itself or another algorithm like Insertion Sort.
3. Merge Step: Once all the subarrays are sorted, they need to be merged back together to obtain the final sorted array. This step involves merging pairs of subarrays and combining them into larger sorted subarrays. This merging can also be parallelized using multiple threads.

Example 1

Input

{5, 2, 8, 4, 1, 9, 3, 7, 6}

Output

1 2 3 4 5 6 7 8 9

Explanation: The output of the code will be the sorted array printed on the console. Given the input array {5, 2, 8, 4, 1, 9, 3, 7, 6}, the code will sort the array using the multi-threaded Merge Sort algorithm and print the sorted array. It indicates that the input array has been successfully sorted in ascending order.

In the given code, the mergeSort method takes the input array, along with the starting and ending indices, to specify the range of the subarray to be sorted. If the subarray size is greater than 1, the method splits the subarray in half, creates two SortTask objects to sort each half separately, and submits them to the thread pool using the submit method. The SortTask class implements the Runnable interface and overrides the run method, which calls mergeSort to sort the respective subarray. After the two subarrays are sorted, the merge method is called to merge them back into a single sorted subarray.

FileName: MergeSortMultiThreaded.java

import java.util.concurrent.*;
public class MergeSortMultiThreaded {
 private static ExecutorService threadPool = Executors.newCachedThreadPool();
 public static void main(String[] args) {
 int[] arr = {5, 2, 8, 4, 1, 9, 3, 7, 6};
 mergeSort(arr, 0, arr.length - 1);
 for (int num : arr) {
 System.out.print(num + " ");
 }
 }
 public static void mergeSort(int[] arr, int low, int high) {
 if (low < high) {
 int mid = (low + high) / 2;
 // Submit left and right subarray sorting tasks to the thread pool
 Future<?> left = threadPool.submit(new SortTask(arr, low, mid));
 Future<?> right = threadPool.submit(new SortTask(arr, mid + 1, high));
 try {
 // Wait for the tasks to complete
 left.get();
 right.get();
 } catch (InterruptedException | ExecutionException e) {
 e.printStackTrace();
 }
 // Merge the sorted subarrays
 merge(arr, low, mid, high);
 }
 }
 public static void merge(int[] arr, int low, int mid, int high) {
 int[] temp = new int[high - low + 1];
 int i = low, j = mid + 1, k = 0;
 // Merge the two subarrays in sorted order
 while (i <= mid && j <= high) {
 if (arr[i] <= arr[j]) {
 temp[k++] = arr[i++];
 } else {
 temp[k++] = arr[j++];
 }
 }
 // Copy remaining elements from the left subarray
 while (i <= mid) {
 temp[k++] = arr[i++];
 }
 // Copy remaining elements from the right subarray
 while (j <= high) {
 temp[k++] = arr[j++];
 }
 // Copy the merged elements back to the original array
 for (i = low, k = 0; i <= high; i++, k++) {
 arr[i] = temp[k];
 }
 }
 // Runnable class representing a sorting task for a subarray
 static class SortTask implements Runnable {
 private int[] arr;
 private int low, high;
 SortTask(int[] arr, int low, int high) {
 this.arr = arr;
 this.low = low;
 this.high = high;
 }
 @Override
 public void run() {
 // Sort the subarray using merge sort algorithm
 mergeSort(arr, low, high);
 }
 }
}

Output

1 2 3 4 5 6 7 8 9

Complexity

The time complexity of the Merge Sort algorithm, using multi-threading, is O(n log n), where 'n' represents the size of the input array. This is because the algorithm divides the array into halves recursively until the base case is reached, and then merges the sorted subarrays back together.

As for space complexity, the multi-threaded Merge Sort implementation uses additional space for the temporary array temp in the merge method. The space complexity is O(n) since the size of the temporary array is directly proportional to the size of the input array.

Therefore, the time complexity of the code is O(n log n), and the space complexity is O(n).