package InfinityJune21.MergeSort;

public class MergeSortExample {

static void printArray(int arr[]) {

int size = arr.length; //finding size of the array

for(int i = 0; i < size; i++) {

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

}

}

static void sort(int arr[], int low, int high) {

if(low < high) {

int middle = (low + high) / 2;

sort(arr, low, middle);

sort(arr, middle + 1, high);

merge(arr, low, middle, high);

}

}

static void merge(int[] arr, int low, int middle, int high) {

//size of the left and right arrays

int size1 = middle - low + 1;

int size2 = high - middle;

//declaring the two arrays

int left[] = new int[size1];

int right[] = new int[size2];

//initializing the two arrays

for(int i = 0; i < size1; i++) {

left[i] = arr[low + i];

}

for(int i = 0; i < size2; i++) {

right[i] = arr[middle + 1 + i];

}

int i = 0, j = 0, k = low;

while(i < size1 && j < size2) {

if(left[i] <= right[j]) {

arr[k] = left[i];

i++;

}

else {

arr[k] = right[j];

j++;

}

k++;

}

while(i < size1) {

arr[k] = left[i];

i++;

k++;

}

while(j < size2) {

arr[k] = right[j];

j++;

k++;

}

}

public static void main(String[] args) {

int arr[] = {23, 18, 29, 30, 10, 49, 99, 45};

int low = 0;

int high = arr.length - 1;

System.out.println("Original Array: ");

printArray(arr); //printing the array

sort(arr, low, high);

System.out.println();

System.out.println("Sorted Array: ");

printArray(arr); //printing the array

}

}