MergeSort

package ds.interview.dataStructure.Algo;
//-----------------------------------------PENDING
import java.util.Arrays;

//https://www.youtube.com/watch?v=TzeBrDU-JaY&list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U&index=5
//MergeSort
public class MergeSort
{

public static void main(String[] args)
{
  int[] arr = {3,5,8,9,1,6,4,2};
  mergesort(arr);
  System.out.println(Arrays.toString(arr));
}

private static void mergesort(int[] arr)
{
  int length = arr.length;
  if(length<2)
  {
  return;
  }
  else
  {
  int mid = length/2; //-------divide
  int[]left = new int[mid];//-------Left Array
  int[]right = new int[length-mid];//-------Right Array
  //Fill Left Array
  for(int i=0;i<left.length;i++)
  {
  left[i] = arr[i];
  }
  //Fill Right Array
  for(int i=mid+1;i<right.length;i++)
  {
  right[i] = arr[i];
  }
  mergesort(left);
  mergesort(right);
  merge(left,right,arr);
 
 
  }

}

private static void merge(int[] left, int[] right, int[] arr)
{

int i=0; //-----for left
int j=0;//------for right
int k=0;//------for main array
while(i<left.length && j<right.length)
{
if(left[i]<right[j])
{
arr[k] = left[i];
i++;k++;
}
else
    if(left[i]>right[j])
{
arr[k] = right[j];
j++;k++;
}
while(i<left.length)
{
arr[k] = left[i];
i++;k++;
}
while(i<left.length)
{
arr[k] = right[j];
j++;k++;
}
}
}

}