**Objective :** Write Merge Sort algorithm to sort elements in an array

**Input:** A unsorted array, arrA[].

**Output :** A sorted array.

**Approach:**

**Divide and Conquer: **In this approach we divide the main problems into smaller problems, solve them and merge the results to get the final result.

**How Divide and conquer works in Merge Sort:**

We divide the elements into two half’s by middle of the array. We solve the left half and right half recursively and merge the results.

Merging:

Once the sorting is done individually on both the half’s, our next task will be merge them. To merge we start with both the arrays at the beginning, pick the smaller one put into array and then compare the next elements and so on.

**Time Complexity : O(nlogn) { O(logn) for dividing and O(n) for merging.**

**Note:**** we can make merging more efficient by implementing these approaches**

**Using Auxiliary Array with copying data –** In this approach you wont create new array everytime for merging instead you create Auxiliary array. This will save memory for you.

**Alternate Merging Between Primary and Auxiliary Array:** This is the best approach for merging. You don’t copy the entire array to auxiliary array for merging instead you do alternate merging between main array and auxiliary array.

Below is the running time comparison between all three approaches

Data Size |
Dynamic Memo Allocation Algo |
Using Auxillary Array with copying data |
Alternate Merging Between Primary and Auxillary Array |

1 Million | 600-630 mili sec | 450-470 mili sec | 400-425 mili sec |

10 million | 6 secs | 4.2 secs | 2.3 secs |

100 million | 56 secs | 46 sec | 18 sec |

**You can find the implementation of all these approaches here – **

GitHub – Three Different Implementations of Merge Sorts

**Complete Code:**

public class MergeSort { | |

private int arrSize; | |

private int [] arrAux; | |

private int [] arrInput; | |

public MergeSort(int [] arrInput){ | |

this.arrInput = arrInput; | |

arrSize = arrInput.length; | |

arrAux = new int [arrSize]; | |

} | |

public int[] mergeSorting(){ | |

sort(0,arrSize–1); | |

return arrInput; | |

} | |

public void sort(int low, int high){ | |

if(low<high){ | |

int mid = low+((high–low))/2; | |

sort(low,mid); | |

sort(mid+1,high); | |

merge(low, mid, high); | |

} | |

} | |

public void merge(int low, int mid, int high){ | |

//copy the entire array in the Auxilary array | |

for(int i=low;i<=high;i++){ | |

arrAux[i] = arrInput[i]; | |

} | |

int i = low; | |

int j = mid+1; | |

int k = low; | |

while(i<=mid && j<=high){ | |

if(arrAux[i]<=arrAux[j]){ | |

arrInput[k]=arrAux[i]; | |

i++; | |

} | |

else{ | |

arrInput[k]=arrAux[j]; | |

j++; | |

} | |

k++; | |

} | |

while(i<=mid){ | |

arrInput[k]=arrAux[i]; | |

i++; | |

k++; | |

} | |

while(j<=high){ | |

arrInput[k]=arrAux[j]; | |

j++; | |

k++; | |

} | |

} | |

public void displayArray(int [] b){ | |

for(int i=0;i<b.length;i++){ | |

System.out.print(" " + b[i]); | |

} | |

} | |

public static void main(String[] args){ | |

int [] a = {2,1,6,3,9,4,5,10}; | |

MergeSort m = new MergeSort(a); | |

int [] b = m.mergeSorting(); | |

m.displayArray(b); | |

} | |

} |

Output :

1 2 3 4 5 6 9 10