MergeSort Algorithm
Introduction
MergeSort is one of the popular and commonly used sorting algorithm. Like QuickSort, MergeSort is a divide and conquer sorting algorithm.
How MergeSort works?
It works by dividing the input array into two halves, then recursively divide the sub arrays also into two halves and continue this process until further division of sub arrays is not possible, then start merging sub arrays in sorting order.
This can be visualized as a top-down approach when dividing the input array, then bottom-up approach for merging the smaller arrays in sorting order. At a high level, below are the steps involved in this algorithm.
- If the given input array length is
, divide the input array into two halves, with one halve with elements fromn
and other halve with elements from[1,..... n/2]
[n/2+1,........n].
- Repeat above step further dividing sub arrays also into two halves recursively until further division is .
- Then, start merging back the sub arrays in sorting order.
MergeSort implementation
Steps involved in this implementation.
-
Given a non empty array
, find the middle index of the array usinginput
,mid = left + (right - left) / 2;
-
Divide input array into two halves, so the two sub arrays will become
and[left,... ,mid]
.[mid+1,... ,right]
- Repeat above two steps in a recursive loop until the sub arrays can't be divided further.
-
When it reaches the end, call
procedure which will merge sub arrays back in sorting order using below steps.merge()
-
Merge procedure takes input as
- input array
- left index
- right index
- middle index - where to split the input array, to get the desired left and right sub arrays.
-
STEP 1:
Create two temporary arrays, call it andleftArray
to hold left and right sub array elements, and then copy fromrightArray
toleft
(inclusive) indices tomid
and copy fromleftArray
tomid+1
indices toright
.rightArray
-
STEP 2:
Start comparing elements from andleftArray
and place them back into input array in the sorting order.rightArray
- STEP 3:
At the end copy any remaining elements from orleftArray
back to input array.rightArray
Note: We are getting middle index using left + (right-left)/2
Integer.MAX_VALUE

package io.cscode.algorithms.sorting;
/**
* MergeSort implementation
*/
public class MergeSort {
/**
* Entry method this sorting algorithm
*
* @param nums input array
*/
public void sort(int[] nums) {
if(nums == null || nums.length==0 ||nums.length==1) {
return;
}
mergeSort(nums, 0, nums.length-1);
}
/**
* Main function that divides array into two halves and recursively calls itself on sub arrays
* when the array cannot be split further, it calls merge() method to start merging on sub arrays.
*
* @param nums input array
* @param left start index
* @param right end index
*/
private void mergeSort(int[] nums, int left, int right) {
if(left < right) {
int mid = left + (right-left)/2;
mergeSort(nums, left, mid); //sort from 1...n/2
mergeSort(nums, mid+1, right); //sort from (n/2)+1 ...n
merge(nums, left, mid, right); //call merge function when input array can't be split be further
}
}
/**
* merge function to merge two sub arrays in sorting order.
*
* @param nums input array
* @param left left index
* @param mid mid index
* @param right right index
*/
private void merge(int[] nums, int left, int mid, int right) {
int n1= mid -left +1; // mid inclusive and indexes starts with 0, so +1
int n2 = right - mid;
int[] leftArray = new int[n1]; // left sub array
int[] rightArray = new int[n2]; // right sub array
for (int i=0; i<n1; i++) {
leftArray[i] = nums[left+i]; // copy from left to mid onto left sub array
}
for (int j=0; j<n2; j++) {
rightArray[j] = nums[mid+1+j]; // copy from mid+1 to right onto right sub array
}
int i=0; // counter to keep track of index for leftArray
int j=0; // counter to keep track of index for rightArray
for (int k=left; k <= right; k++) {
if(i<leftArray.length && j<rightArray.length) {
if(leftArray[i] <=rightArray[j]) {
nums[k] = leftArray[i];
i++;
} else {
nums[k] = rightArray[j];
j++;
}
} else {
//copy any remaining elements in leftArray or rightArray into input array
if(i < leftArray.length) {
nums[k] = leftArray[i];
i++;
}
if(j < rightArray.length) {
nums[k] = rightArray[j];
j++;
}
}
}
}
}
Complexity analysis:
To sort an array of n
merge()
MergeSort implementation source code can be found here on