Merge Sort: Implement the folowing function in Java: - a merge sort function - a
ID: 3868286 • Letter: M
Question
Merge Sort:
Implement the folowing function in Java:
- a merge sort function
- a function to test if an array is sorted
- a driver program to sort arrays provied by user input
- Allow the driver program to accept a text file with arrays to be sorted then output each result
Merge Sort Lab Directions Implement the following functions in Java: . a merge sort function a function to test if an array is sorted A driver program to sort arrays provided by user input Allow the driver program to accept a text file with arrays to be sorted, then output each result. Input File Format The first line of the input file will be the number of arrays contained in the file. Subsequent lines will each contain a list of numbers, separated by a space. An example input file: 4 25 5 29 6 12 64 23 11 32 94 12 42 23 55 The driver program would read the input file, sort each of the 3 arrays, then output each result.Explanation / Answer
MergeSort.java
/* Java program for Merge Sort */
class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
}
TestClass.java
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class TestClass {
public static void main(String args[])
{
BufferedReader br = null;
FileReader fr = null;
try {
//br = new BufferedReader(new FileReader(FILENAME));
fr = new FileReader("NumberRows.txt");
br = new BufferedReader(fr);
String sCurrentLine;
sCurrentLine = br.readLine();
int i=Integer.parseInt(sCurrentLine);
while ((sCurrentLine = br.readLine()) != null) {
String arr[]=sCurrentLine.split(" ");
int array[]=new int[arr.length];
for(int j=0;j<arr.length;j++)
{
array[j]=Integer.parseInt(arr[j]);
}
System.out.println("Given Array");
MergeSort.printArray(array);
MergeSort ob = new MergeSort();
ob.sort(array, 0, array.length-1);
System.out.println(" Sorted array");
MergeSort.printArray(array);
System.out.println();
}
} catch (IOException e) {
e.printStackTrace();
}
finally {
try {
if (br != null)
br.close();
if (fr != null)
fr.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
}