Merge Sort using Extra Storage in Java

  1. public class ExtraStorageMergeSort{  
  2.     public static void main(String a[]){  
  3.         int i;  
  4.         int array[] = {12,9,4,99,120,1,3,10};  
  5.         int array1[] = new int[array.length];  
  6.         System.out.println("\n\n       RoseIndia\n\n");  
  7.         System.out.println("       Extra Strorage Space Merge Sort\n\n");  
  8.         System.out.println("Values Before the sort:\n");  
  9.         for(i = 0; i < array.length; i++)  
  10.             System.out.print( array[i]+"  ");  
  11.         System.out.println();  
  12.         mergeSort_srt(array,0, array.length-1,array1);  
  13.         System.out.print("Values after the sort:\n");  
  14.         for(i = 0; i <array.length; i++)  
  15.         System.out.print(array1[i]+"  ");  
  16.         System.out.println();  
  17.         System.out.println("PAUSE");  
  18.     }  
  19.       
  20.     public static void mergeSort_srt(int array[], int low, int high, int array1[]){  
  21.         if(low >= high) {  
  22.             return;  
  23.         }  
  24.   
  25.         int middle = (low+high) / 2;  
  26.         mergeSort_srt(array, low, middle, array1);  
  27.         mergeSort_srt(array, middle+1, high, array1);  
  28.         int k, t_low = low, t_high = middle+1;  
  29.         for(k = low; k <= high; k++)  
  30.             if ((t_low <= middle) && ((t_high > high) || (array[t_low] < array[t_high]))) {  
  31.                 array1[k] = array[t_low++];  
  32.             }  
  33.             else {  
  34.                 array1[k] = array[t_high++];  
  35.             }  
  36.         for(k = low; k <= high; k++) {  
  37.             array[k] = array1[k];  
  38.         }  
  39.     }  
  40. }