Home Java Beginners Arrayexamples Extra Storage Merge Sort in Java
Questions:Ask|Latest

 
 

Share on Google+Share on Google+

Extra Storage Merge Sort in Java

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

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.printarray[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+high2;
  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.

Advertisement

If you enjoyed this post then why not add us on Google+? Add us to your Circles



Liked it!  Share this Tutorial


Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.

Posted on: May 28, 2007

Related Tutorials

Ask Questions?    Discuss: Extra Storage Merge Sort in Java  

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments
vamsi
June 14, 2012
collection framework

program on binary conversion by using collection
DMCA.com