What is merge sort write an algorithm of merge sort?
Answers
- Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sublists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
Answer:
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++];
}
while(j < rs){
arr[k++] = right[j++];
}
}
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(java.util.Arrays.toString(arr));
}
}
Explanation: