# Extra Storage Merge Sort in Java

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

Ads

Tutorials

# 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 = 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.

Advertisements

Ads
Share on Google+

# Extra Storage Merge Sort in Java

Posted on: May 28, 2007 If you enjoyed this post then why not add us on Google+? Add us to your Circles

Advertisements

Ads

Related Tutorials

Discuss: Extra Storage Merge Sort in Java

Post your Comment

Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):

Comments:1
vamsi
June 14, 2012
collection framework

program on binary conversion by using collection

Ads

Ads