Submit your Java codes via Blackboard. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
(25: optional after two required) [Counting inversions: programming] Implement the sort-and-count algorithm discussed in class and shown below. (A pair of numbers in the input array L is said to be inverted if the number on the left is larger than the number on the right.)
Sort-and-Count(L) {
if list L has one element return 0 and the list L;
Divide the list into two halves A and B; (rA, A) Sort-and-Count(A);
(rB, B)Sort-and-Count(B);
(rB, L) Merge-and-Count(A, B); return r = rA + rB + r and the sorted list L;
}
Your program code must implement this divide-and-conquer algorithm as a recursive function named “Sort-and-Count”; code of the combine function Merge-and-Count can be in a separate function named as such or included within the Sort-and-Count code. Your program should prompt for an input file name, and then read from the file a list of array elements one line at a time and display on the screen the number of inversions in the array and the sorted array elements. See sample_input.txt and sample_output.txt for example of input and display output. Submit your source codes via Blackboard. Program codes should be not only working but also neatly organized and well commented. No point will be given to program codes that do not work, and there will be points deducted for codes that are hard to read.
