. Write a JAVA program to sort for an element in a given list of elements using merge sort.
Answers
class Mrg_sorting
{
void merge(int arry[], int ln, int m1, int r)
{
int n1 = m1- ln + 1;
int n2 = r - m1;
int LL[] = new int [n1];
int RR[] = new int [n2];
for (int i=0; i<n1; ++i)
LL[i] = arry[ln + i];
for (int j=0; j<n2; ++j)
RR[j] = arry[m1 + 1+ j];
int i = 0, j = 0;
int k = ln;
while (i < n1 && j < n2)
{
if (LL[i] <= RR[j])
{
arry[k] = LL[i];
i++;
}
else
{
arry[k] = RR[j];
j++;
}
k++;
}
while (i < n1)
{
arry[k] = LL[i];
i++;
k++;
}
while (j < n2)
{
arry[k] = RR[j];
j++;
k++;
}
}
void sort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2;
sort(arr, l, m);
sort(arr , m+1, r);
merge(arr, l, m, r);
}
}
static void print_Array(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int array[] = {12, 11, 13, 5, 6, 7};
System.out.println("Given Array");
print_Array(array);
Mrg_sorting ob = new Mrg_sorting();
ob.sort(array, 0, array.length-1);
System.out.println("\n the sorted array is");
print_Array(array);
}
}
The JAVA program is as follows.
import java.util.*;
public class MergerSort { public static void main(String[] args //Unsorted array Integer[] a = { 2, 6, 3, 5, 1 };
//Call merge sort mergeSort(a);
//Check the output which is sorted array System.out.println(Arrays.toString(a));
} @SuppressWarnings("rawtypes") public static Comparable[] mergeSort(Comparable[] list) { //If list is empty;
no need to do anything if (list.length <= 1) { return list;
} //Split the array in half in two parts Comparable[] first = new Comparable[list.length / 2];
Comparable[] second = new Comparable[list.length - first.length]; System.arraycopy(list, 0, first, 0, first.length);
System.arraycopy(list, first.length, second, 0, second.length);
//Sort each half recursively mergeSort(first); mergeSort(second);
//Merge both halves together, overwriting to original array merge(first, second, list);
return list;} @SuppressWarnings({ "rawtypes", "unchecked" }) private static void merge(Comparable[] first, Comparable[] second, Comparable[] result) { //Index Position in first array - starting with first element int iFirst = 0;
//Index Position in second array - starting with first element int iSecond = 0;
//Index Position in merged array - starting with first position int iMerged = 0;
//Compare elements at iFirst and iSecond, //and move smaller element at iMerged while (iFirst < first.length && iSecond < second.length) { if (first[iFirst].compareTo(second[iSecond]) < 0) { result[iMerged] = first[iFirst]; iFirst++;
} else { result[iMerged] = second[iSecond]; iSecond++;
} iMerged++;
} //copy remaining elements from both halves - each half will have already sorted elements System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst); System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond); } }