Please use java.

Test the sorting algorithm as follows.

For input sizes n = 500, n = 1,000, n = 1,500, , n = 10,000 [Thats 20 different values of n]

Create an array Ais of size n.

Fill the array with n random integers.

Create a copy of the array, Ams.

Pass the array Ais to your insertion sort and record the number of comparisons.

Pass the array Ams to your mergesort and record the number of comparisons.

Then produce a graph which shows for each value of n, the number of comparisons for each sort You should also plot n log n and n2 on the same graph to compare their shape with the insertion sort and mergesort results.

Insertion sort code:

public class InsertionSort {

void sort(int a[]) { int n = a.length; for (int i = 1; i < n; ++i) { int m = a[i]; int j = i - 1; while (j >= 0 && a[j] > m) { a[j + 1] = a[j]; j = j - 1; } a[j + 1] = m; } } static void printArray(int a[]) { int n = a.length; for (int i = 0; i < n; ++i) System.out.print(a[i] + " "); System.out.println(); } public static void main(String args[]) { int a[] = { 5,4,1,3,2 }; System.out.println("Given array: 5 4 1 3 2"); InsertionSort i = new InsertionSort(); i.sort(a); System.out.println("Sorted array:"); printArray(a); } }

Merge Sort code:

public class MergeSort { void merge(int a[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int A1[] = new int[n1]; int A2[] = new int[n2]; for (int i = 0; i < n1; ++i) A1[i] = a[l + i]; for (int j = 0; j < n2; ++j) A2[j] = a[m + 1 + j]; int i = 0, j = 0; int k = l; while (i < n1 && j < n2) { if (A1[i] <= A2[j]) { a[k] = A1[i]; i++; } else { a[k] = A2[j]; j++; } k++; } while (i < n1) { a[k] = A1[i]; i++; k++; } while (j < n2) { a[k] = A2[j]; j++; k++; } } void sort(int a[], int l, int r) { if (l < r) { int m =l+ (r-l)/2; sort(a, l, m); sort(a, m + 1, r); merge(a, l, m, r); } } static void printArray(int a[]) { int n = a.length; for (int i = 0; i < n; ++i) { System.out.print(a[i] + " "); } System.out.println(); } public static void main(String args[]) { int a[] = { 5,4,1,3,2 }; System.out.println("Given Array:"); printArray(a); MergeSort m = new MergeSort(); m.sort(a, 0, a.length - 1); System.out.println(" Sorted array:"); printArray(a); } }