title: Merge-sort using Multi-threading
body: <p>I tried to parallelize merge-sort using multi-threading.Here is my code (please forgive if it poorly implemented.I did not care about the space-complexity of the program). I am achieving the sorted array.My question is:Will this process actually reduce the time taken to sort an array of large size?What all modifications are needed to make it efficient and is it o any use?</p>
  
  <pre><code>import java.io.IOException;
  import java.util.Arrays;
  import java.util.Random;
  import java.util.Scanner;
  
  public class Merge {
      public static int[] inputArray;
      public static int[] arr1;
      public static int[] arr2;
      public static int[] arr3;
      public static int t1_status=0;
      public static int t2_status=0;
  
      public static void main(String[] args) throws IOException{
  
          System.out.println("Enter the length of the array");
  
          Scanner in =new Scanner(System.in);
  
          int arraySize=in.nextInt();
  
          inputArray = new int[arraySize];
  
          Random rand=new Random();
  
          for(int i=0;i&lt;arraySize;i++)
          {
              inputArray[i]=rand.nextInt(100);
          }
  
          //diving the original array into two subarrays
  
          arr1=Arrays.copyOfRange(inputArray, 0, inputArray.length/2);
  
          arr2=Arrays.copyOfRange(inputArray, (inputArray.length)/2,inputArray.length);
          //printing the original array
          System.out.print("The original array is array is ");
  
          for(int h:inputArray)
          {
              System.out.println(h);
          }
  
          Thread t1=new Thread(new Runnable(){
                  public void run() 
                  {
                      mergeSort(arr1);
                      System.out.println("t1 started");
                  }
  
              });
          Thread t2=new Thread(new Runnable(){
                  public void run()
                  {
                      mergeSort(arr2);
                      System.out.println("t2 started");
                  }
  
              });
          //starting threads
          t1.start();
          t2.start();
  
          try {
              t1.join();
              t2.join();
          }
          catch (InterruptedException e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
          if(t1.isAlive())
          {
              t1_status=1;
          }
          if(t2.isAlive())
          {
              t2_status=1;
          }
          t1.stop();
          t2.stop();
  
          arr3=new int[inputArray.length];
  
          merge(arr3,arr1,arr2);//merging arr1 and arr2.At this point both arr1 and arr2 are sorted.
  
          System.out.println("The sorted array is ");
          for(int m:arr3)
          {
              System.out.print(m);
              System.out.print(" ");
          }
          System.out.println(" ");
      }
  
      static void mergeSort(int[] A)
      {
          if (A.length &gt; 1) 
          {
              int q = A.length/2;
  
              int[] leftArray = Arrays.copyOfRange(A, 0, q);
              int[] rightArray = Arrays.copyOfRange(A,q,A.length);
              mergeSort(leftArray);
              mergeSort(rightArray);
              merge(A,leftArray,rightArray);
          }
      }
      //merge function
  
      static void merge(int[] a, int[] l, int[] r) {
          int totElem = l.length + r.length;
  
          int i,li,ri;
          i = li = ri = 0;
          while ( i &lt; totElem) {
              if ((li &lt; l.length) &amp;&amp; (ri&lt;r.length)) {
                  if (l[li] &lt; r[ri]) {
                      a[i] = l[li];
                      i++;
                      li++;
                  }
                  else {
                      a[i] = r[ri];
                      i++;
                      ri++;
                  }
              }
              else {
                  if (li &gt;= l.length) {
                      while (ri &lt; r.length) {
                          a[i] = r[ri];
                          i++;
                          ri++;
                      }
                  }
                  if (ri &gt;= r.length) {
                      while (li &lt; l.length) {
                          a[i] = l[li];
                          li++;
                          i++;
                      }
                  }
              }
          }
  
          if(t1_status==1){arr1=a;}
          else if(t2_status==1){arr2=a;}
          else{arr3=a;}
      }
  }
  </code></pre>