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>_
|