Question

what is merge sort
and algorithm

Answer 1

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

Answer 2

Answer:

import java.util.Arrays;

public class Main

{

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

       int ls = left.length;

       int rs = right.length;

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

           while(i < ls && j < rs){

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

                   arr[k] = left[i];

                   i++;

               }

               else{

                   arr[k] = right[j];

                   j++;

               }

               k++;

           }

       while(i < ls){

           arr[k] = left[i];

           i++;

           k++;

       }

       while(j < rs){

           arr[k] = right[j];

           j++;

           k++;

       }

   }

   static void merge_sort(int[] arr){

       int n = arr.length;

           if(n < 2){

               return;

           }

       int mid = n/2;

       int[] left = new int[mid];

       int[] right = new int[n-mid];

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

               left[i] = arr[i];

           }

           for(int i = mid; i < n; i++){

               right[i-mid] = arr[i];

           }

       merge_sort(left);

       merge_sort(right);

       merge(arr,left,right);

   }

public static void main(String[] args) {

 int[] arr = {9,8,4,5,2,7,1,3,0,2};

 merge_sort(arr);

 System.out.println(Arrays.toString(arr));

}

}

Explanation: