Merge Sort in Java

In this tutorial you will learn about merge sort in Java with program and example.

Merge sort has gained its popularity because of its runtime and simplicity. It will exhibit best runtime for sorting. Now we will see algorithm, program with example for merge sort.

It uses divide-and-conquer policy to sort input elements.

Divide phase: It will divide problem into smaller sub problems of same kind.

Conquer phase: In this phase we will solve each sub problem.

Combine phase: In this we will combine solutions to get solution for our main problem.

Merge Sort Example

Let us see working of merge sort with example.

Divide phase: If it takes input as array it will recursively divide input array into two halves until the sub array size is 1. Let us see how division will be done recursively.

First it will divide input into two halves.

Now recursively call merge sort on each sub array for further division.

After reaching sub array length 1, it will stop dividing. Because it cannot split further.

Conquer phase:  Generally combine phase is not needed. Conquering phase will take care of that. In conquering phase we should solve each sub array. Now we will see how to solve each sub problem.

We will select 2 sub problems for merging. In merging, we will compare the elements of both sub problems and minimum element will be placed first in merged sub array if we are doing sorting for ascending order. If it is descending order then we will put maximum.

Here sub arrays 1 and 8 were selected. Those 2 sub arrays are of size 1. Already sorted we should combine both of them into one array by comparing the elements in both the arrays.

If we are sorting array in ascending order then minimum element should be kept in the merged array as shown in above.

Let us see for sub problems 6, 2 for better understanding. 2 is minimum element so we will keep 2 first in merged array.

Next 6 will be kept in sorted sub array.

Now these length 2 sorted sub arrays will contribute solution for length 4 sub array.

Now left sub array is sorted. So call merge sort function on right sub array. Same process will be repeated for right sub array also. It will divide the right sub array further as in case of left sub array.

Merging operation will start by combining the small sorted sub arrays. Same procedure will be repeated.

Now right sub array also sorted. We should merge these 2 sub arrays in the same fashion as we did for left right sub arrays.

We got the solution for our original problem by solving the sub problems. This strategy is very much useful in programming practices.

Program for Merge Sort in Java

class MergeSort{
	public void mergeSort(int arr[],int l,int r)
	{
		if(l<r) //(l<r) condition will hold good until getting singleton arrays
		{
			int mid;   
			mid = (l+r)/2;
			mergeSort(arr,l,mid); //calling merge sort on left sub array
			mergeSort(arr,mid+1,r);// calling merge sort on right sub array
			merge(arr,l,mid,r);// merge operation 
		}
	}
	
	public void merge(int arr[],int l,int mid,int r)
	{
		int n1=(mid-l+1);  //getting size of left sub array
		int n2=r-mid;     //getting size of right sub array
		int  left[]=new int[n1]; 
		int right[]= new int[n2];
		int i;
		
		for (i=0;i<n1;i++)
		{
			left[i]=arr[l+i];   
		}
		
		for (i=0;i<n2;i++)
		{
			right[i]=arr[mid+1+i];
		}
		
		int li,ri,ai;     
		li=0;	//left index
		ri=0;	//right index
		ai=l;	//array index
		
		while (li<n1 && ri <n2)
		{
			if(left[li]<=right[ri])	// minimum element will be placed in sorted sub array
			{
				arr[ai]= left[li];
				ai++;
				li++;
			}
			else
			{
				arr[ai]= right[ri];
				ai++;
				ri++;
			}
		}
		
		while(li < n1)	// copy remaining elements of left sub array into the merged array
		{
			arr[ai]= left[li];
			ai++;
			li++;
		}
		
		while(ri < n2)	//copy remaining elements of right sub array into the merged array
		{
			arr[ai]= right[ri];
			ai++;
			ri++;
		}
	}
	
	public void printArray(int arr[])
	{
		int n = arr.length;
		
		for (int i=0; i<n; ++i)
			System.out.print(arr[i] + " ");
		
		System.out.println();
	}
	
	public static void main(String args[])
	{
		int arr[]={1,8,6,2,3,5,4,9};
		MergeSort obj= new MergeSort();
		
		System.out.println("array before applying merge sort");
		obj.printArray(arr);
		
		obj.mergeSort(arr,0,7);
		
		System.out.println("\narray after applying merge sort");
		obj.printArray(arr);
	}
}

Output

array before applying merge sort
1 8 6 2 3 5 4 9

array after applying merge sort
1 2 3 4 5 6 8 9

Runtime Analysis

In each step problem will be divided into 2 sub problems of half size and we are merging them. For merge operation it will take O(n) time in worst case.

Recursive formula T(n) = 2T(n/2) + O(n)

If we solve this equation we will get O(n logn) where n is input size.

In best case and worst case merge sort will exhibit same complexity.

Space Complexity

It will use 2 auxiliary arrays for sorting.

But at max it will use space equal to input size only. We can say that space complexity also as O(n)

Comment below if you have any queries related to above tutorial for merge sort in Java.