### Mergesort in Java using divide and conquer

Merge sort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two collections and these are again sorted via mergesort. Once the two collections are sorted then the result is combined .Merge sort will take the middle of the collection and takes then the two collection for the next iteration of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of the both to insert it into a new collection.In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while mergesort requires a copy.

 Thanks Wikipedia
Algorithm :
Conceptually, a merge sort works as follows
1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly Merge sub lists to produce new sublists until there is only 1 sublist remaining. (This will be the sorted list.)

Java version of the Mergesort is given below:

 16 8 24 4 12 20 28 2 6 10 14 18 22 26 30

Array of integers, named array

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Index of array element

``` * To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package mergesort;

/**
*
* @author ACHCHUTHAN
*/
public class MergeSort {
int array[];
int size;

public MergeSort(int n) {
size=n;
//create array with size n
array=new int[n];
//asign value into the array
for (int i=0;i<n;i++){
array[i]=(int) Math.round(Math.random()*89+10);
}
}

public int getSize() {
return size;
}

public void merge(int left, int mid, int right) {
int temp [] =new int[right-left+1];
int i = left;
int j = mid+1;
int k = 0;
while (i <= mid && j <= right) {
if (array[i] <= array[j]) {
temp[k] = array[i];
k++;
i++;
} else { //array[i]>array[j]
temp[k] = array[j];
k++;
j++;
}
}
while(j<=right) temp[k++]=array[j++];
while(i<=mid) temp[k++]=array[i++];

for(k=0;k<temp.length;k++) array[left+k]=temp[k];
}
public void merge_sort(int left,int right){
// Check if low is smaller then high, if not then the array is sorted
if(left<right){
// Get the index of the element which is in the middle
int mid=(left+right)/2;
// Sort the left side of the array
merge_sort(left,mid);
// Sort the right side of the array
merge_sort(mid+1,right);
// Combine them both
merge(left,mid,right);
}

}
public void print(){
System.out.println("Contents of the Array");
for(int k=0;k<15;k++) {
System.out.print(array[k]+" | ");
}
System.out.println();

}
public static void main(String args[]){
MergeSort m=new MergeSort(15);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
m.print();
m.merge_sort(0,m.getSize()-1);
System.out.println("After Sort > > > > > > > > > > > >");
m.print();
System.out.println("=======+============+=======+============+=========");
MergeSort m2=new MergeSort(25);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
m2.print();
m2.merge_sort(0,m2.getSize()-1);
System.out.println("After Sort > > > > > > > > > > > >");
m2.print();
System.out.println("=======+============+=======+============+=========");
MergeSort m3=new MergeSort(30);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
m3.print();
m3.merge_sort(0,m3.getSize()-1);
System.out.println("After Sort > > > > > > > > > > > >");
m3.print();
System.out.println("=======+============+=======+============+=========");

}
}
```
Output of this program
run:
Before Sort <<<<<<<<<<<<<<<<<<<<<
Contents of the Array
59 | 42 | 28 | 34 | 95 | 72 | 48 | 27 | 46 | 20 | 28 | 61 | 25 | 81 | 30 | After Sort > > > > > > > > > > > >
Contents of the Array
20 | 25 | 27 | 28 | 28 | 30 | 34 | 42 | 46 | 48 | 59 | 61 | 72 | 81 | 95 |
=======+============+=======+============+=========
Before Sort <<<<<<<<<<<<<<<<<<<<<
Contents of the Array 16
| 67 | 78 | 34 | 50 | 26 | 79 | 82 | 35 | 44 | 72 | 97 | 69 | 55 | 47 |
After Sort > > > > > > > > > > > >
Contents of the Array 10 | 16 | 18 | 26 | 27 | 30 | 34 | 35 | 44 | 44 | 47 | 50 | 55 | 56 | 67 | =======+============+=======+============+=========
Before Sort <<<<<<<<<<<<<<<<<<<<<
Contents of the Array 95 | 49 | 74 | 29 | 56 | 77 | 26 | 92 | 19 | 28 | 21 | 20 | 97 | 19 | 82 |
After Sort > > > > > > > > > > > >
Contents of the Array 19 | 19 | 20 | 21 | 26 | 28 | 29 | 30 | 38 | 43 | 48 | 49 | 52 | 56 | 62 | =======+============+=======+============+=========
BUILD SUCCESSFUL (total time: 0 seconds)