Like QuickSort, Merge Sort also divide and conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, left, mid, right) is key process that assumes that arr[left..mid] and arr[mid+1..right] are sorted and merges the two sorted sub-arrays into one.
See following java implementation details to understand it correctly.
MergeSort(arr[], left, right)
If right > left
1. Find the middle point to divide the array into two halves:
middle mid = (left+right)/2
2. Call mergeSort for first half:
Call MergeSort(arr, left, mid)
3. Call mergeSort for second half:
Call MergeSort(arr, mid+1, right)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, left, mid, right)
Please go through the following graphical representation to understand it.
The image shows the complete merge sort process for an example array {12, 35, 87, 26, 9, 28, 7}.
In the following diagram we can see that the array is divide recursively
into two parts till its size become 1.
Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.
Merge Sort Code in Java given below:
package dataStructures;
class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(int arr[], int left, int mid, int right)
{
// Find sizes of two subarrays to be merged
int n1 = mid - left + 1;
int n2 = right - mid;
System.out.println(n1 + " " + n2);
/* Create temp arrays */
int Left[] = new int [n1];
int Right[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
Left[i] = arr[l + i];
for (int j=0; j<n2; ++j)
Right[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = Left[i];
i++;
}
else
{
arr[k] = Right[j];
j++;
}
k++;
}
/* Copy remaining elements of Left[] if any */
while (i < n1)
{
arr[k] = Left[i];
i++;
k++;
}
/* Copy remaining elements of Right[] if any */
while (j < n2)
{
arr[k] = Right[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int left, int right)
{
if (left < right)
{
// Find the middle point
int mid = (left+right)/2;
// Sort first and second halves
sort(arr, left, mid);
sort(arr , mid+1, right);
// Merge the sorted halves
merge(arr, l, mid, right);
}
}
/* print array function of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
//Main method
public static void main(String args[])
{
int arr[] = {6334, 4098, 7968, 4523, 277, 6956, 4560, 2062, 5705, 5743, 879, 5626, 9961, 491, 2995, 741, 4827};
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
printArray(arr);
}
}
Output:
Given Array
6334 4098 7968 4523 277 6956 4560 2062 5705 5743 879 5626 9961 491 2995 741 4827
Sorted array
277 491 741 879 2062 2995 4098 4523 4560 4827 5626 5705 5743 6334 6956 7968 9961
Time complexity of Merge Sort is : O(nLogn) in all 3 cases (worst, average and best).
I hope you guys understand the cocept of merge sort in java..
Thanks for reading..!
Happy Coding .. !
Thank you..!
THE NUCLEAR GEEKS 
One thought on “Merge Sort in Java”