Latest Tutorials| Questions and Answers|Ask Questions?|Site Map



Home Java Beginners Arrayexamples Merge Sort In Java

Related Tutorials


 
 

Share on Google+Share on Google+

Merge Sort In Java

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

Merge Sort in Java

     

Introduction

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

In merge sorting algorithm unsorted values are divided into two equal parts iteratively. Then merge both parts and sort it. Then again merge the next part and sort it. Do it iteratively
until  the values are not in sorted order. In merge sorting the number of elements must be even. The merge sorting is invented by John von Neumann in 1945 .
The complexity of the merge sorting is in worst-case O(n log n) and in average case O(n log n).
  
Code description:
In merge sort split the array values in halves recursively until each half has only single  element. Merge the two 1/2 values together and sort the values. Do same steps iteratively until the values are not sorted. 

Working of 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 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:Merge two values  and sort the values

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 four values and sort the values
A[2] A[1] A[0] A[3],...................................................................................A[n-1]
..................................................................................................................
..................................................................................................................
.................................................................................................................
Step3:Merge n values and sort the values
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 mergeSort{
  public static void main(String a[]){
  int i;
  int array[] {12,9,4,99,120,1,3,10};
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Selection 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);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  public static void mergeSort_srt(int array[],int lo, int n){
  int low = lo;
  int high = n;
  if (low >= high) {
  return;
  }

  int middle = (low + high2;
  mergeSort_srt(array, low, middle);
  mergeSort_srt(array, middle + 1, high);
  int end_low = middle;
  int start_high = middle + 1;
  while ((lo <= end_low&& (start_high <= high)) {
  if (array[low< array[start_high]) {
  low++;
  else {
  int Temp = array[start_high];
  for (int k = start_high- 1; k >= low; k--) {
  array[k+1= array[k];
  }
  array[low= Temp;
  low++;
  end_low++;
  start_high++;
  }
  }
  }  
}

Output of the example:

C:\array\sorting>javac mergeSort.java
C:\array\sorting>java mergeSort
       RoseIndia
       Selection 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

Discuss: Merge Sort In Java   View All Comments

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments:10
suraj Tripathi
July 29, 2011
computer

thanks......... good work..........
Mohd Ishahak
September 15, 2011
Java Technology

plz send me informatoin related jave and thanks to give us motivation in java..
Tugdual de Kerviler
February 21, 2013
Wrong algorithm

Please remove this wrong algorithm from the Internet. This is not a correct merge sort : the insertion of an element in the merge part is in O(n) which makes the algorithm run in O(n²log(n)).
AKGN
November 23, 2011
Download link error

the given download link given for merge sort is different. Its a download link of bubble sort program. Please update it.
shrikant
December 12, 2011
wrong algo

even though the sorting works ... it dosent look like an implementation of the merge sort
Chin Hang
January 16, 2013
Computer Programming (Mergesort in String)

Can you show me how to merge two class database using string . For example , First class database consist of 8 students and the second consist of 10 students . Thank you :)
MANISH SHARMA
February 15, 2012
Why Selectin Sort is written in SOP

Why Selectin Sort is written in SOP
OctopusPrim3
March 23, 2012
sir please write a code using with this

public class isort{ public static void main(String args[]) { int arr[] = {2,1,4,5,3}; int temp; System.out.print ("THE NUMBERS ARE; "); for (int b = 0; b<=4;b++){ System.out.print(arr[b]+" "); } System.out.println(); for (int x = 0; x<=3;x++){ for (int y = x+1; y<=1;y++){ System.out.println("CHECK INDEX"+x+"&"+y); System.out.print("VALUE AFTER CHECK: "); if (arr[x] > arr[y]){ temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } for (int a=2;a>0;a++){ } for (int b=0;b<=4;b++){ System.out.print(arr[b]+" "); } System.out.println(); System.out.println(); } } } }
Harry
June 2, 2012
Filename is Bubblesort.java

Downloading the example downloads a Bubblesort algorithm, not mergesort.
nagaraj
December 29, 2013
this file name is bubble sort.java

Downloading the example downloads a Bubblesort algorithm, not mergesort
DMCA.com