Signup/Sign In

Merge Sort in Java

Merge Sort is an efficient and stable sorting algorithm. It is based on a divide and conquer algorithm approach. In this tutorial, we will learn more about Merge Sort and its implementation in Java.

Merge Sort Algorithm

Merge Sort uses the Divide and Conquer technique for sorting. The Divide part of the algorithm includes splitting the input array into two smaller arrays. The smaller arrays are again split into two halves.

This process continues recursively, as long as the arrays contain more than one element. Remember that an array having just a single element is already sorted. Merge Sort takes advantage of this property and uses it in the conquer part of the algorithm.

The algorithm for this part is summarized by the steps below.

  • If the input array length is less than 2, then return.
  • Else, calculate the middle index of the array and split the first half recursively.
  • Then recursively split the right half of the array.
  • Merge the left and right half of the array into a single sorted array.

Dividing input array into smaller arrays

After dividing the input array, the algorithm combines or merges these smaller-sized arrays back into a single sorted array. The merging will always take place on two sorted arrays. This happens because the merging process will start after dividing the input array into single-element arrays.

Merging sorted arrays to form the complete sorted array

Let's consider an example to better understand the merging of arrays. Suppose we have two sorted arrays, [4, 7, 9] and [2, 3, 8]. The following steps explain how these two arrays will be merged to form a single sorted array.

Initially, we have a pointer at the beginning of both arrays. We will repeat the following steps until we run out of elements from either array.

merge sort

The elements that the two array pointers are referencing are compared. The first element of the second array is smaller than the first element of the first array(2<4). So we add the smaller element to our final sorted array and move the pointer of the second array one place to the left.

merge sort

Again, the referenced element of the second array is smaller(3<4). So 3 is added to the final array, and the pointer of the second array moves forward.

merge sort

Now the referenced element of the first array is smaller(4<8). So 4 is added to the result array, and the pointer of the first array moves forward to 7.

merge sort

7 is smaller than 8, so it is added to the result array, and the pointer of the first array moves on to 9.

merge sort

The referenced element of the second array is smaller than the referenced element of the first array(8<9). So 8 is added to the final sorted array. The second array pointer cannot move forward as we ran out of elements from the second array. So the loop terminates.

merge sort

All elements of the other array are added to the final array. Our final array will look like [2, 3, 4, 7, 8, 9].

Merge Sort Implementation in Java

Let's implement merge sort in Java. We will use two methods to implement the merge sort algorithm. A mergeSort() method will recursively divide the input array and will call the merge() method on them. The merge() method will contain the merging logic.

The mergeSort() method code is shown below.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx)
{
	if (startIdx >= endIdx) //array contains just a single element
		return; 

	int midIdx = startIdx + (endIdx - startIdx) / 2; //middle index
	mergeSort(arrToSort, startIdx, midIdx); //Divide the left half recursively
	mergeSort(arrToSort, midIdx + 1, endIdx); //Divide the right half recursively
			
	merge(arrToSort, startIdx, midIdx, endIdx); //merge the left and right half
}
	

The merge() method code is shown below.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx)
{
	int[] leftArr = new int[midIdx - startIdx + 1]; 
	int[] rightArr = new int[endIdx - midIdx];
		
	//Initializing the left and right arrays
	for(int i=0; i<leftArr.length; i++)
		leftArr[i] = arrToSort[startIdx + i];
		
	for(int i=0; i<rightArr.length; i++)
		rightArr[i] = arrToSort[midIdx + i + 1];
		
	//merging the left and right arrays into a single sorted array
	int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
	while((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length))
	{
		if(leftArr[leftArrIdx] < rightArr[rightArrIdx])
		{
			arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
			leftArrIdx += 1;
		}
		else
		{
			arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
			rightArrIdx += 1;
		}
		sortedArrIdx += 1;
	}
		
	//Adding the rest of the elements of left array if present
	while(leftArrIdx < leftArr.length)
	{
		arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
		leftArrIdx += 1;
		sortedArrIdx += 1;
	}
		
	//Adding the rest of the elements of right array if present
	while(rightArrIdx < rightArr.length)
	{
		arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
		rightArrIdx += 1;
		sortedArrIdx += 1;
	}
}

Let's run a few examples to check if our methods work correctly.

public static void main(String[] args)
{
	int[] arr1 = { 4, 2, 3, 0, 1, 7, 6 };
	mergeSort(arr1, 0, arr1.length - 1);
	System.out.println(Arrays.toString(arr1));
		
	int[] arr2 = {};
	mergeSort(arr2, 0, arr2.length - 1);
	System.out.println(Arrays.toString(arr2));
		
	int[] arr3 = {7};
	mergeSort(arr3, 0, arr3.length - 1);
	System.out.println(Arrays.toString(arr3));
		
	int[] arr4 = {-1, -7, 0, 11, 102, -11};
	mergeSort(arr4, 0, arr4.length - 1);
	System.out.println(Arrays.toString(arr4));
}


[0, 1, 2, 3, 4, 6, 7]
[]
[7]
[-11, -7, -1, 0, 11, 102]

Time and Space Complexity

The recursive relation for the merge sort algorithm will be T(n) = 2T(n/2) + O(n). This leads to the time complexity of O(nLogn). Remember that merge sort is a stable algorithm and its time complexity will not change. Its best-case, worst-case, and average-case time complexities will always be equal to O(nLogn).

We require additional space, which is equal to the size of the input array. This makes the Space Complexity equal to O(n), where n is the length of the input array.

Summary

Merge Sort is one of the most efficient algorithms out there and it can be easily implemented using recursion. It uses the Divide and Conquer paradigm to sort an array. It is a very stable algorithm and its time complexity remains the same for all three cases(best, worst, and average).



About the author:
I am a 3rd-year Computer Science Engineering student at Vellore Institute of Technology. I like to play around with new technologies and love to code.