Merge Sort is a sorting algorithm.
We keep dividing the array till it is divided into the smallest unit (1 element per array). After dividing we sort the element with the adjacent element and merge them. This is done for each element and finally after merging we get the sorted array. The image below shows the graphical representation of the merge sort.
Below is the code for merge sort which uses recursion :
public class MergeSort {
public static void mergeSort(int[] array, int first, int length) {
int low = first;
int high = length;
if (low >= high) {
return;
}
int middle = (low + high) / 2;
mergeSort(array, low, middle);
mergeSort(array, middle + 1, high);
int low1 = middle;
int high1 = middle + 1;
while ((first <= low1) && (high1 <= high)) {
if (array[low] < array[high1]) {
low++;
} else {
int temp = array[high1];
for (int k = high1 - 1; k >= low; k—) {
array[k + 1] = array[k];
}
array[low] = temp;
low++;
low1++;
high1++;
}
}
}
public static void main(String[] args) {
int[] array = { 2, 3, 6, 10, 35, 15, 7, 8, 20, 17 };
System.out.print(“Original Array => “);
for (int i = 0; i < array.length; i++) {
System.out.print(“\t” + array[i]);
}
System.out.println();
mergeSort(array, 0, array.length - 1);
System.out.print(“Sorted Array => “);
for (int i = 0; i < array.length; i++) {
System.out.print(“\t” + array[i]);
}
}
}
