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.
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.
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.
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.
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.
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.
7 is smaller than 8, so it is added to the result array, and the pointer of the first array moves on to 9.
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.
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).
