The purpose of this assignment is to implement a sorting alg

The purpose of this assignment is to implement a sorting algorithm on different datastructures and to also compare relative performance.

You are to write two Java Classes using Generics to perform the sorting.

MyArrayListSort.java

MyLinkedListSort.java

Both Classes should support the following features:

void sort( List < T > inputList, Boolean ascending);

The Generic T must be Compareable.

The inputList should be sorted based on the ascending flag (ascending == True means increasing)

The sorting algorithm to be implemented is Merge Sort.

MyArrayListSort: Should use the java.util.ArrayList

MyLinkedListSort: Should use the java.util.LinkedList

The program should include a driver class (Main). This driver class should:

Take a single commandline argument which consists of either a local(relative to the location of the jar) file, or an absolute file path (and name) to the input file.

This file will be a CSV (comma separated value) list of values (integervalues, though your sorting should allow for lists of any compareable).

Each line of the input file will correspond to a list which is to be sorted.

Sort each list in ascending fashion.

After each list is sorted the total time for your sorting should be savedfor later reporting. This should be done for each of the two sorting classes.

Use System.nanoTime() before and after each call to the sorting methods.

After the input has been sorted by each of the classes, the driver funcionshould use the java.util.collections: Collections.sort(list) and record the time. Use an ArrayList as input for this call.

After the list has been sorted by both of the classes the following shouldbe printed: The number of elements, the sorting time of the arrayList, the sorting time of the linked list, the sorting time of the Collections package

This should be done on a one line per input line.

This should be printed both the System.out, and to a file named output.txt at the same path location of the input file.

An additional text file should be created, named sortedInput.text.

This file is to contain the sorted list from each of your implementedsorting methods. The sorted lists should both be on their own line with a blank line between different input lists (so the first list would take up 3 lines, the second would start on line 4 etc).

Solution

public class MyMergeSort {

private int[] array;
private int[] tempMergArr;
private int length;

public static void main(String a[]){

int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
MyMergeSort mms = new MyMergeSort();
mms.sort(inputArr);
for(int i:inputArr){
System.out.print(i);
System.out.print(\" \");
}
}

public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
doMergeSort(0, length - 1);
}

private void doMergeSort(int lowerIndex, int higherIndex) {

if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
doMergeSort(lowerIndex, middle);
doMergeSort(middle + 1, higherIndex);
mergeParts(lowerIndex, middle, higherIndex);
}
}

private void mergeParts(int lowerIndex, int middle, int higherIndex) {

for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}

}
}