Java thread Programming - Multithreaded Java Program: Sorting an Array of Integers

Java Thread: Exercise-3 with Solution

Write a Java program that sorts an array of integers using multiple threads.

The program divides the sorting task among multiple threads and perform parallel sorting to improve the performance of sorting large arrays.

Sample Solution:

Java Code:

import java.util.Arrays;

public class ParallelSort {
  private static final int ARRAY_SIZE = 400;
  private static final int NUM_THREADS = 4;

  public static void main(String[] args) {
    int[] array = createArray();
    System.out.println("Before sorting: " + Arrays.toString(array));

    Thread[] threads = new Thread[NUM_THREADS];
    int segmentSize = ARRAY_SIZE / NUM_THREADS;

    for (int i = 0; i < NUM_THREADS; i++) {
      int startIndex = i * segmentSize;
      int endIndex = (i == NUM_THREADS - 1) ? ARRAY_SIZE - 1 : (startIndex + segmentSize - 1);
      threads[i] = new Thread(new SortTask(array, startIndex, endIndex));
      threads[i].start();
    }

    for (Thread thread: threads) {
      try {
        thread.join();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }

    mergeSort(array, 0, ARRAY_SIZE - 1);

    System.out.println("After sorting: " + Arrays.toString(array));
  }

  private static int[] createArray() {
    int[] array = new int[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++) {
      array[i] = (int)(Math.random() * 400); // Generate random numbers between 0 and 400
    }
    return array;
  }

  private static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
      int mid = (left + right) / 2;
      mergeSort(array, left, mid);
      mergeSort(array, mid + 1, right);
      merge(array, left, mid, right);
    }
  }

  private static void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
      if (array[i] <= array[j]) {
        temp[k++] = array[i++];
      } else {
        temp[k++] = array[j++];
      }
    }

    while (i <= mid) {
      temp[k++] = array[i++];
    }

    while (j <= right) {
      temp[k++] = array[j++];
    }

    System.arraycopy(temp, 0, array, left, temp.length);
  }

  static class SortTask implements Runnable {
    private int[] array;
    private int startIndex;
    private int endIndex;

    public SortTask(int[] array, int startIndex, int endIndex) {
      this.array = array;
      this.startIndex = startIndex;
      this.endIndex = endIndex;
    }

    @Override
    public void run() {
      Arrays.sort(array, startIndex, endIndex + 1);
    }
  }
}

Sample Output:

Before sorting: [317, 153, 98, 262, 171, 100, 371, 350, 386, 162, 139, 160, 69, 59, 331, 305, 12, 312, 190, 385, 355, 259, 9, 96, 217, 340, 313, 46, 47, 213, 200, 121, 94, 79, 64, 47, 91, 113, 192, 268, 135, 362, 256, 72, 299, 181, 22, 174, 360, 217, 149, 238, 67, 226, 261, 91, 26, 17, 292, 300, 107, 314, 389, 75, 222, 322, 129, 186, 133, 356, 129, 134, 313, 276, 376, 133, 352, 95, 205, 50, 152, 303, 296, 4, 281, 328, 282, 110, 16, 359, 70, 266, 143, 226, 353, 69, 395, 291, 197, 395, 171, 188, 346, 177, 179, 146, 319, 202, 71, 105, 399, 182, 367, 398, 396, 30, 170, 251, 390, 361, 75, 127, 39, 334, 294, 92, 157, 272, 120, 112, 323, 383, 122, 29, 397, 291, 392, 290, 87, 390, 39, 359, 299, 223, 88, 325, 35, 232, 46, 264, 69, 247, 392, 147, 56, 39, 345, 138, 223, 299, 114, 207, 74, 27, 160, 234, 0, 125, 44, 101, 49, 263, 216, 351, 169, 341, 346, 316, 27, 318, 27, 154, 389, 109, 141, 351, 73, 100, 17, 230, 184, 374, 214, 152, 387, 48, 235, 74, 309, 68, 185, 337, 23, 138, 281, 130, 146, 32, 82, 337, 322, 114, 399, 253, 129, 258, 256, 123, 74, 183, 158, 328, 229, 195, 177, 54, 332, 385, 88, 26, 84, 340, 252, 319, 68, 87, 76, 8, 31, 238, 196, 304, 21, 392, 86, 171, 0, 117, 310, 344, 110, 341, 37, 245, 145, 297, 185, 19, 365, 274, 168, 145, 367, 177, 198, 25, 161, 234, 141, 365, 389, 350, 102, 2, 282, 193, 15, 30, 167, 257, 293, 336, 32, 170, 330, 304, 75, 310, 248, 116, 98, 16, 245, 151, 51, 318, 322, 280, 384, 358, 362, 354, 147, 131, 382, 305, 129, 253, 179, 194, 270, 135, 92, 103, 126, 57, 214, 93, 155, 130, 107, 54, 149, 63, 128, 9, 354, 399, 392, 253, 13, 394, 306, 311, 289, 122, 338, 96, 367, 128, 8, 301, 347, 334, 269, 278, 250, 134, 158, 121, 265, 373, 39, 145, 107, 183, 83, 212, 190, 33, 83, 254, 296, 229, 66, 259, 56, 159, 45, 84, 385, 219, 32, 393, 258, 98, 139, 167, 266, 122, 14, 377, 280, 146, 157, 376, 190, 342, 145, 161, 44, 4, 296, 222, 142, 10, 1, 117, 40, 382]
After sorting: [0, 0, 1, 2, 4, 4, 8, 8, 9, 9, 10, 12, 13, 14, 15, 16, 16, 17, 17, 19, 21, 22, 23, 25, 26, 26, 27, 27, 27, 29, 30, 30, 31, 32, 32, 32, 33, 35, 37, 39, 39, 39, 39, 40, 44, 44, 45, 46, 46, 47, 47, 48, 49, 50, 51, 54, 54, 56, 56, 57, 59, 63, 64, 66, 67, 68, 68, 69, 69, 69, 70, 71, 72, 73, 74, 74, 74, 75, 75, 75, 76, 79, 82, 83, 83, 84, 84, 86, 87, 87, 88, 88, 91, 91, 92, 92, 93, 94, 95, 96, 96, 98, 98, 98, 100, 100, 101, 102, 103, 105, 107, 107, 107, 109, 110, 110, 112, 113, 114, 114, 116, 117, 117, 120, 121, 121, 122, 122, 122, 123, 125, 126, 127, 128, 128, 129, 129, 129, 129, 130, 130, 131, 133, 133, 134, 134, 135, 135, 138, 138, 139, 139, 141, 141, 142, 143, 145, 145, 145, 145, 146, 146, 146, 147, 147, 149, 149, 151, 152, 152, 153, 154, 155, 157, 157, 158, 158, 159, 160, 160, 161, 161, 162, 167, 167, 168, 169, 170, 170, 171, 171, 171, 174, 177, 177, 177, 179, 179, 181, 182, 183, 183, 184, 185, 185, 186, 188, 190, 190, 190, 192, 193, 194, 195, 196, 197, 198, 200, 202, 205, 207, 212, 213, 214, 214, 216, 217, 217, 219, 222, 222, 223, 223, 226, 226, 229, 229, 230, 232, 234, 234, 235, 238, 238, 245, 245, 247, 248, 250, 251, 252, 253, 253, 253, 254, 256, 256, 257, 258, 258, 259, 259, 261, 262, 263, 264, 265, 266, 266, 268, 269, 270, 272, 274, 276, 278, 280, 280, 281, 281, 282, 282, 289, 290, 291, 291, 292, 293, 294, 296, 296, 296, 297, 299, 299, 299, 300, 301, 303, 304, 304, 305, 305, 306, 309, 310, 310, 311, 312, 313, 313, 314, 316, 317, 318, 318, 319, 319, 322, 322, 322, 323, 325, 328, 328, 330, 331, 332, 334, 334, 336, 337, 337, 338, 340, 340, 341, 341, 342, 344, 345, 346, 346, 347, 350, 350, 351, 351, 352, 353, 354, 354, 355, 356, 358, 359, 359, 360, 361, 362, 362, 365, 365, 367, 367, 367, 371, 373, 374, 376, 376, 377, 382, 382, 383, 384, 385, 385, 385, 386, 387, 389, 389, 389, 390, 390, 392, 392, 392, 392, 393, 394, 395, 395, 396, 397, 398, 399, 399, 399]

Explanation:

In the above exercise,

• The ParallelSort class is defined to perform parallel sorting.
• The program begins by defining the array size (ARRAY_SIZE) and the number of threads to use (NUM_THREADS).
• The main() method is the program's entry point. It first creates an array of integers using the createArray() method, which generates random numbers between 0 and 400.
• The array's initial state isrinted using Arrays.toString().
• An array of threads, threads, is created to handle sorting. The array is divided into segments, and each thread is assigned a specific segment to sort. The size of each segment is determined by dividing the array size by the number of threads.
• Loops create and start each thread. The SortTask class represents the sorting task performed by each thread. It takes the array, start index, and end index as input parameters and uses Arrays.sort() to sort the assigned segment of the array.
• Another loop waits for all threads to complete execution using join().
• After the parallel sorting operation is complete, the entire array is sorted using the mergeSort() method, which implements the merge sort algorithm. The merge() method is a helper method used in the merge sort algorithm to merge two sorted subarrays.

Finally, the sorted array is printed using Arrays.toString().

Flowchart:

Java Code Editor:

Improve this sample solution and post your code through Disqus

Previous: Find and Print Even-Odd Numbers with Threads.
Next: Multithreaded Java Program: Matrix Multiplication.