MergeSort Program

Merge Sort:

public class MergeSort2 {

    public static void main(String args[]) {
        int[] arr = {1,12,3,8,2,1,7,9};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
   
    public static void mergeSort(int[] arr, int start, int end) {
        if(start<end) {                               //check start < mid then find mid and divide arr in parts 
            int mid = (start + end)/2 ;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid+1, end);
            merge(arr, start, mid, end); //merge
        }
    }
   
    public static void merge(int[] arr, int start, int mid, int end) {
        int p = start ;
        int q = mid+1;
       
        int[] localArr = new int[end-start+1];
        int k = 0;
        for(int i=start;i<=end;i++) {
            if(p>mid) {
                localArr[k] = arr[q];
                k++;
                q++;
            }else if(q>end) {
                localArr[k] = arr[p];
                k++;
                p++;
            }else if(arr[p]<arr[q]) {
                localArr[k] = arr[p];
                p++;
                k++;
            }else {
                localArr[k]  =arr[q];
                q++;
                k++;
            }
        }
       
        for(int i=0;i<localArr.length;i++) {
            arr[start]  = localArr[i];
            start++;
        }
       
       
    }
   
}

How merge method work:
take an example below
[1,12 ,3,8 ||||||| ,2,1,7,9] start = 0,mid = 1,end = 3
we want to merge 0 to 3

p = 0
q=  mid+1 = 2;
take localarr of size end-start+1 = 4
k=0
loop---> start to < = end
if p reaches to mid then only right part need to insert localarr
if(p>mid) {
                localArr[k] = arr[q];
                k++;
                q++;
            }
if q reaches to end then only left part need to insert into localarr
else if(q>end) {
                localArr[k] = arr[p];
                k++;
                p++;
            }

if arr[p] <arr[q] it means need to insert p position element to localarr and increemt p

else if(arr[p]<arr[q]) {
                localArr[k] = arr[p];
                p++;
                k++;
            }

if arr[p]>arr[q] it means need to insert q position element to localarr and increment q
 else {
                localArr[k]  =arr[q];
                q++;
                k++;
            }

loop exit

now need to insert localarr to original array
  for(int i=0;i<localArr.length;i++) {
            arr[start]  = localArr[i];
            start++;
        }