# Merge Sort in Java

## Introduction:

Merge sort is a divide and conquer algorithm.

Conceptually, a merge sort works as follows

1. Divide the unsorted list recursively into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly Merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

The program of Merge Sort in java is given below:

## Java Code for Merge Sort:

```
import java.io.*;
public class MergeSort{
private int[] arr; //stores array of elements
private int[] temp; //used for temporarily storing elements
private int num; //number of elements

public static void main(String[] args){
MergeSort x=new MergeSort();
x.sort();
}

public void sort(){
try{
System.out.print("Enter total no. of numbers: ");
arr=new int[num];
temp=new int[num];
System.out.println("Enter the numbers: ");
for(int i=0;i<num;i++){
System.out.print("Enter number "+i+": ");
}
}catch(IOException e){
e.printStackTrace();
}
mergeSort(0,num-1);

for(int i=0;i<num;i++)
System.out.println(i+" : "+arr[i]);
}

public void mergeSort(int low,int high){
//merge sort
if(low<high){
int mid=(low+high)/2; //finds the mid position of the array
mergeSort(low,mid); //merge sort the first part
mergeSort(mid+1,high); //merge sort the last part
merge(low,mid,high); //merge the two parts
}
}

public void merge(int low,int mid,int high){
//merge the two parts
for(int i=low;i<=high;i++)
temp[i]=arr[i];
int i=low;
int j=mid+1;
int k=low;
//selects the smaller element from the two parts
//and fill the array accordingly
while(i<=mid && j<=high){
if(temp[i]<=temp[j]){
arr[k++]=temp[i];
i++;
}
else{
arr[k++]=temp[j];
j++;
}
}
//fills the rest of the elements into the array
while(i<=mid)
arr[k++]=temp[i++];
}
}

```

## Conclusion:

If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm. In sorting n objects, merge sort has an average and worst case performance of O(n log n).

References: http://en.wikipedia.org/wiki/Merge_sort

If you have any questions regarding the post please use the comments below.

Categories
Previous article

Next article