Extra Storage Merge Sort in Java

Introduction
In this example we are going to sort integer values of an array using extra storage merge sort.

In extra storage merge sorting algorithm  the unsorted values divide into two equal parts iteratively and create an array for store data value in extra storage. Then merge the two parts , sort it and store into an array .Then again merge the next part , sort it and store into an array. Do it iteratively until  the values are not in sorted order. In this sorting the number of elements must be even.

Code description:
In extra storage  is similar to merge sort .But in extra storage merge sort the sorted values are stored in an other array.

Working of extra storage merge sort algorithm:
Say we have an array unsorted  A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by storage merge sort algorithm to sort the values of an array.

Step1:Spliting the values of array
Divide the values into two equal 1/2
A[0],A[1],A[2].........A[n/2-1]   &  A[n/2]....... .................A[n-1], A[n]

 Again divide two equal 1/2
A[0] a[1]A[2]..............A[(n/2-1)/2-1] &  A[(n/2-1)/2]............A[n/2-1],
A[n/2].............A[(2n-1)/2-1]  & a[(2n-1)/2].............A[n-1],A[n]
..........................................................................................................................
..........................................................................................................................
........................................................................................................................
A[0] & A[1] & A[2]& A[3],..............................................................A[n-1]& A[n]

Step2:Mergesets of  two values, sort the values and store into a different array

A[0],A[1] & A[2],A[3]&..................................................................&A[n-1],A[n]
If A[1]<A[0],A[]<A[3]........................................................................A[n-1]>A[n]
then
A[1]A[0],A[2]A[3],...............................................................................A[n]A[n-1]
Step3:Merge sets of four values, sort the values and store into a different array
A[2] A[1] A[0] A[3],...................................................................................A[n-1]
..................................................................................................................
..................................................................................................................
.................................................................................................................
Step3:Merge n values, sort the values and store into a different array
A[2]A[6]......................................................................................................A[n-5]

Where n must be even number.

Steps of Merge Sort:

Say unsorted  an array values are:
12,9,4,99,120,1,3,10



The code of the program :

public class ExtraStorageMergeSort{   public static void main(String a[]){   int i;   int array[] = {12,9,4,99,120,1,3,10};   int array1[] = new int[array.length];   System.out.println("\n\n RoseIndia\n\n");   System.out.println(" Extra Strorage Space Merge Sort\n\n");   System.out.println("Values Before the sort:\n");   for(i = 0; i < array.length; i++)   System.out.print( array[i]+"  ");   System.out.println();   mergeSort_srt(array,0, array.length-1,array1);   System.out.print("Values after the sort:\n");   for(i = 0; i <array.length; i++)   System.out.print(array1[i]+"  ");   System.out.println();   System.out.println("PAUSE");   }      public static void mergeSort_srt(int array[], int low, int high, int array1[]){   if(low >= high) {   return;   }   int middle = (low+high) / 2;   mergeSort_srt(array, low, middle, array1);   mergeSort_srt(array, middle+1, high, array1);   int k, t_low = low, t_high = middle+1;   for(k = low; k <= high; k++)   if ((t_low <= middle) && ((t_high > high) || (array[t_low] < array[t_high]))) {   array1[k] = array[t_low++];   }   else {   array1[k] = array[t_high++];   }   for(k = low; k <= high; k++) {   array[k] = array1[k];   }   } }

Output of the example:

C:\array\sorting>javac ExtraStorageMergeSort.java C:\array\sorting>java ExtraStorageMergeSort RoseIndia Extra Strorage Space Merge Sort Values Before the sort: 12 9 4 99 120 1 3 10 Values after the sort: 1 3 4 9 10 12 99 120 PAUSE C:\array\sorting>_

Download this example.