Please make sure the code is written in JAVA and not in any other language. Only needs to add the "complete this method" part.

Save the following java program into xxxxxp4.java and do as follow:

1. Do not modify the main method, except writing your name in line 83 and OPTIONAL part).
2. Implement external sort:

for the sort phase use normal sort,

for the merge phase use two way merge to merge n sorted files (merge2way(n)),

for array sort use heapsort.

Also write merge(f1, f2, f3) to merge two sorted files f1 and f2 into f3..

1. OPTIONAL EXTRA POINT: Write mergenway(n) method and print execution time of both merges for initial input file over 10MB data. (100 Pts)
2. A sample input is as follow:Note:Fist input is max array size for sort

10 84 82 52 80 96 85 75 75 82 87 92 89 57 94 93 92 63 99 87

72 73 56 74 50 84 62 72 55 86 75 74 100 83 60 53 68 89 67 66

65 72 94 73 54 98 96 85 75 75 82 87 92 89

To compile: javac xxxxxp4.java

To execute: java xxxxxp4 < any data file name

import java.util.*; import java.io.*;

// Implementing external sort:

// For sort phase using normal sort and

// for merge phase using 2way merge.

public class xxxxxp4 {

// class used for search

int heap[], M; //M is largest array size

//use a short word for System.out to save typing

PrintStream prt = System.out;

// print file formatted k integers per line

private void prtfile(String fn, int k) {

//declare variables

int i = 0, x;

prt.printf(" \t%s:", fn);

try {

Scanner inf = new Scanner(new File(fn));

while (inf.hasNext()) {

//read an input from fname

x = inf.nextInt();

prt.printf("%3d ", x);

i++;

if (i % k == 0) prt.printf(" \t");

} // endwhile

// close file

inf.close();

} catch (Exception e) {

prt.printf(" Ooops! Read Exception: %s", e); }

} // end prtfile

// print n files

private void prtfiles(int n, int k) {

int i;

String fname;

for (i = 1; i <= n; i++) {

fname = "F" + i + ".txt";

prtfile(fname, k);

}

} // end prtfiles

// normalsort, creating arrays of size n

private int normalsort() {

// complete this method

} // end normalsort

//2way merge n sorted files

private void merge2way(int n) {

// complete this method

} // end merge2way

//OPTIONAL nway merge n sorted files

private void mergenway(int n) {

// complete this method

} // end mergenway

//merge 2 sorted files f1, f2 into f3

private void merge(String f1, String f2, String f3) {

// complete this method

} // end merge

//Heapsort heap[] with n integers

private void heapsort(int n) {

//complete this method

} // end sort

public static void main(String[] args) throws Exception {

int n, k = 15; // print 15 integers per line

xxxxxp4 srt = new xxxxxp4();

n = srt.normalsort(); // n is no. of sorted files created

srt.prtfiles(n, k);

System.out.printf(" Overall %4d sorted files are created", n);

//srt.merge2way(n); // Merging n sorted files using 2-way merge

//OPTIONAL srt.mergenway(n); Merging n sorted files using n-way merge

//OPTIONAL Print execution time of both merges

//MAKE SURE TO WRITE YOUR NAME IN NEXT LINE

System.out.printf(" \tAuthor: Date: " +

java.time.LocalDate.now());

} // end main

} // end xxxxxp4