Merge Sort in Java

arnab

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(){
 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 try{
 System.out.print("Enter total no. of numbers: ");
 num=Integer.parseInt(br.readLine());
 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+": ");
 arr[i]=Integer.parseInt(br.readLine());
 }
 }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. :-P