In this tutorial, we shall have a deeper insight into the merge sort algorithm in Java.
The sorting mechanism is one of the most widely known and used approach as a part of our day to day activities and the manner in which every individual uses it to solve complex problems.
The merge sort algorithm is based on the divide-and-conquer approach where the bigger or largest chunk of the problem is divided into small subparts and consequently those are divided up till one of such sub-part gets solvable.
Implementation of Merge sort:
For the implementation let us write a mergesort function which takes input parameters as the array and the length of the array. Let us start by recognizing our base case, which is when the array is checked up as single element items, i.e., the length of each subpart is 1. For other cases, we keep calling for the recursive steps. The recursive step is for finding the middle index and create two arrays. The mergesort function is again called for the two newly created arrays and subsequently their sub-arrays.
Now comes the call for merge function where the actual sorting takes place as the merge action happens. The merge function compares the values of the elements of the two sub-arrays one at a time and starts placing the smaller element into the input array.
Therefore, the merge function takes input parameters as the sub-arrays and their starting and ending indices both.
Once the end of one sub-array is reached the elements of the other arrays are just copied into the input array giving us the final sorted array.
The time complexity for the Merge sort algorithm is O(n logn) because the merge sort first breaks the array into two halves and then subsequent division into halves follow, later followed by a linear merging of the elements. The complexity is the same for all the cases, best, average, worst, since the array no matter what the case is broken up into parts and then merged as single element items.
The sorting mechanism is one of the most widely known and used approach as a part of our day to day activities and the manner in which every individual uses it to solve complex problems.
The merge sort algorithm is based on the divide-and-conquer approach where the bigger or largest chunk of the problem is divided into small subparts and consequently those are divided up till one of such sub-part gets solvable.
Implementation of Merge sort:
For the implementation let us write a mergesort function which takes input parameters as the array and the length of the array. Let us start by recognizing our base case, which is when the array is checked up as single element items, i.e., the length of each subpart is 1. For other cases, we keep calling for the recursive steps. The recursive step is for finding the middle index and create two arrays. The mergesort function is again called for the two newly created arrays and subsequently their sub-arrays.
public static void mergeSort(int[] a, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] l = new int[mid];
int[] r = new int[n - mid];
for (int i = 0; i < mid; i++) {
l[i] = a[i];
}
for (int i = mid; i < n; i++) {
r[i - mid] = a[i];
}
mergeSort(l, mid);
mergeSort(r, n - mid);
merge(a, l, r, mid, n - mid);
}
Now comes the call for merge function where the actual sorting takes place as the merge action happens. The merge function compares the values of the elements of the two sub-arrays one at a time and starts placing the smaller element into the input array.
Therefore, the merge function takes input parameters as the sub-arrays and their starting and ending indices both.
Once the end of one sub-array is reached the elements of the other arrays are just copied into the input array giving us the final sorted array.
public static void merge(
int[] a, int[] l, int[] r, int left, int right) {
int i = 0, j = 0, k = 0;
while (i < left && j < right) {
if (l[i] <= r[j]) {
a[k++] = l[i++];
}
else {
a[k++] = r[j++];
}
}
while (i < left) {
a[k++] = l[i++];
}
while (j < right) {
a[k++] = r[j++];
}
}
The time complexity for the Merge sort algorithm is O(n logn) because the merge sort first breaks the array into two halves and then subsequent division into halves follow, later followed by a linear merging of the elements. The complexity is the same for all the cases, best, average, worst, since the array no matter what the case is broken up into parts and then merged as single element items.