write a java program to sort an element in given list of elements using merge sort
Answers
Answer:
Java Program
public class MyMergeSort
{
void merge(int arr[], int beg, int mid, int end)
{
int l = mid - beg + 1;
int r = end - mid;
intLeftArray[] = new int [l];
intRightArray[] = new int [r];
for (int i=0; i<l; ++i)
LeftArray[i] = arr[beg + i];
for (int j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];
int i = 0, j = 0;
int k = beg;
while (i<l&&j<r)
{
if (LeftArray[i] <= RightArray[j])
{
arr[k] = LeftArray[i];
i++;
}
else
{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i<l)
{
arr[k] = LeftArray[i];
i++;
k++;
}
while (j<r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}
void sort(int arr[], int beg, int end)
{
if (beg<end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[])
{
intarr[] = {90,23,101,45,65,23,67,89,34,23};
MyMergeSort ob = new MyMergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
for(int i =0; i<arr.length;i++)
{
System.out.println(arr[i]+"");
}
}
}
OUTPUT
Sorted array
Sorted array 23
Sorted array 2323
Sorted array 232323
Sorted array 23232334
Sorted array 2323233445
Sorted array 232323344565
Sorted array 23232334456567
Sorted array 2323233445656789
Sorted array 232323344565678990
Sorted array 232323344565678990101
Answer:
import java.util.*;
class mergeSort
{
static void merge(int[] arr , int[] leftHalf , int[] rightHalf)
{
int rightSize = rightHalf.length;
int leftSize = leftHalf.length;
int i = 0 , j = 0 , k = 0;
while(i < leftSize && j < rightSize)
{
if(leftHalf[i] <= rightHalf[j])
{
arr[k] = leftHalf[i];
i++;
}
else
{
arr[k] = rightHalf[j];
j++;
}
k++;
}
while(i < leftSize)
{
arr[k] = leftHalf[i];
i++;
k++;
}
while(j < rightSize)
{
arr[k] = rightHalf[j];
j++;
k++;
}
}
static void mergeSort(int[] arr)
{
int len = arr.length;
if(len < 2)
{
return;
}
int midIndex = len / 2;
int[] leftHalf = new int[midIndex];
int[] rightHalf = new int[len - midIndex];
for(int i = 0; i < midIndex; i++)
{
leftHalf[i] = arr[i];
}
for(int i = midIndex; i < len; i++)
{
rightHalf[i - midIndex] = arr[i];
}
mergeSort(leftHalf);
mergeSort(rightHalf);
merge(arr , leftHalf , rightHalf);
}
public static void main(String[] args)
{
int[] arr = {9,8,4,5,2,7,1,3,0,2};
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
}
Explanation: