# Merge Sort In Java

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

Tutorials

# 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.print( array[i]+"  ");   System.out.println();   mergeSort_srt(array,0, array.length-1);   System.out.print("Values after the sort:\n");   for(i = 0; i = high) {   return;   }   int middle = (low + high) / 2;   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>_`

# Merge Sort In Java

Related Tutorials

Discuss: Merge Sort In Java   View All Comments

Subject (*):

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

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