Implement the mergesort algorithm using Java generics. Description First, downlo
ID: 3759742 • Letter: I
Question
Implement the mergesort algorithm using Java generics.
Description
First, download the driver and dictionary files, and place them in your project directory
Create a class MergeSorter.java that implements the mergesort algorithm in a generic way (i.e. over items that extend the Java Comparable interface). You may use this file as a template. Your goal is twofold:
• Genericize the mergesorter class using ArrayLists rather than arrays.
• Fill in the recursive portion of the mergesort algorithm within the `mergesort' method (annotated for you)
In addition, the driver times the speed of your mergesort algorithm. After you have completed the above, you should try using LinkedLists rather than ArrayLists, and see how the time changes.
NOTE: Be careful with your parameters to ensure they will only take types of List, and not ArrayList
Example Dialog
Checking merge algorithm:
Success!
Initial (int) array of size 76066 is sorted: false
Mergesort: 214.883256 ms
Integer array sort successful.
Simple string sort:
the quick brown fox jumps over the lazy dog
brown dog fox jumps lazy over quick the the
Initial (String) array of size 57578 is sorted: false
Mergesort: 192.520276 ms
String array sort successful.
Note
The driver is randomized, so your output will be different
Explanation / Answer
Solution in java for merge sort algorthim is below. please let me know if any modificatios are required
import java.lang.*;
public class MergeSort {
public static <T extends Comparable<T>> void sort(T[] a) {
mergesort(a, 0, a.length-1);
}
private static <T extends Comparable<T>> void mergesort (T[] a, int i, int j) {
if (j-i < 1) return;
int mid = (i+j)/2;
mergesort(a, i, mid);
mergesort(a, mid+1, j);
merge(a, i, mid, j);
}
@SuppressWarnings("unchecked") private static <T extends Comparable<T>> void merge(T[] a, int p, int mid, int q) {
Object[] tmp = new Object[q-p+1];
int i = p;
int j = mid+1;
int k = 0;
while (i <= mid && j <= q) {
if (a[i].compareTo(a[j])<=0)
tmp[k] = a[i++];
else
tmp[k] = a[j++];
k++;
}
if (i <= mid && j > q) {
while (i <= mid)
tmp[k++] = a[i++];
} else {
while (j <= q)
tmp[k++] = a[j++];
}
for (k = 0; k < tmp.length; k++) {
a[k+p] = (T)(tmp[k]);
}
}
public static void main(String[] args) {
Integer[] a = new Integer[5];
a[0] = new Integer(2);
a[1] = new Integer(1);
a[2] = new Integer(4);
a[3] = new Integer(3);
a[4] = new Integer(-1);
MergeSort.sort(a);
for (int i = 0; i < a.length; i++)
System.out.println(a[i].toString());
}
}