Merge Sort: The gateway to Divide and Conquer
2 min readJul 4, 2021
public class MergeSort {
// mergesort -> to divide the array
// conquer -> to compare the element and combine them
public void merge(int arr[], int left, int mid, int right){
//size of two temporary sub arrays
int n1 = mid - left+1;
int n2 = right - mid;
// Created two temporary sub arrays
int[] L = new int[n1];
int[] R = new int[n2];
//Let's copy the original content of array into temporary arrays
for(int i = 0; i < n1; i++)
L[i] = arr[left + i];
for(int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
//Index for the first element of subarray
int i=0, j=0;
//index for the original array
int k = left;
// Merge logic
while(i<n1 && j<n2){
if(L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else{
arr[k] = R[j];
j++;
}
k++;
}
//printArray(arr);
//System.out.println("i: "+ i + " j: "+ j);
//If left subarray elements are left
while(i < n1){
arr[k] = L[i];
i++;
k++;
}
// If right subarray elements are left
while(j < n2){
arr[k] = R[j];
j++;
k++;
}
}
public void sort(int arr[], int left, int right){
if(right > left){
int mid = left + ((right - left)/2);
sort(arr, left, mid);
sort(arr, mid+1, right);
//Merge the sorted halves
merge(arr, left, mid, right);
}
}
public void printArray(int[] arr){
for(int i=0;i < arr.length;i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
MergeSort ms = new MergeSort();
int arr[] = { 12, 11, 13, 5, 6, 7 };
System.out.println("Given array is: ");
ms.printArray(arr);
ms.sort(arr, 0, arr.length-1);
System.out.println("Sorted array is: ");
ms.printArray(arr);
}
}