IN JAVA PLEASE

Implement the insertion sort algorithm.

Implement the merge sort algorithm.

Test the sorting algorithm as follows.

For input sizes n = 5,000, n = 10,000, n = 15,000, ..., n = 100,000

generate an array Ais of size n.

Fill the array with n random integers.

generate 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.

Below are the algorithms i have implemented:

public class InsertionSort {

/*Function to sort array using insertion sort*/

void sort(int arr[])

{

int n = arr.length;

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

int key = arr[i];

int j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

}

/* A utility function to print array of size n*/

static void printArray(int arr[])

{

int n = arr.length;

for (int i = 0; i < n; ++i)

System.out.print(arr[i] + " ");

System.out.println();

}

// Driver method

public static void main(String args[])

{

int arr[] = { 12, 11, 13, 5, 6 };

InsertionSort ob = new InsertionSort();

ob.sort(arr);

printArray(arr);

}

}

public class MergeSort

{

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

// Find sizes of two subarrays to be merged

int n1 = m - l + 1;

int n2 = r - m;

/* Create temp arrays */

int L[] = new int[n1];

int R[] = new int[n2];

/*Copy data to temp arrays*/

for (int i = 0; i < n1; ++i)

L[i] = arr[l + i];

for (int j = 0; j < n2; ++j)

R[j] = arr[m + 1 + j];

/* Merge the temp arrays */

// Initial indexes of first and second subarrays

int i = 0, j = 0;

// Initial index of merged subarry array

int k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

}

else {

arr[k] = R[j];

j++;

}

k++;

}

/* Copy remaining elements of L[] if any */

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

/* Copy remaining elements of R[] if any */

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}

}

// Main function that sorts arr[l..r] using

// merge()

void sort(int arr[], int l, int r)

{

if (l < r) {

// Find the middle point

int m =l+ (r-l)/2;

// Sort first and second halves

sort(arr, l, m);

sort(arr, m + 1, r);

// Merge the sorted halves

merge(arr, l, m, r);

}

}

/* A utility function to print array of size n */

static void printArray(int arr[])

{

int n = arr.length;

for (int i = 0; i < n; ++i)

System.out.print(arr[i] + " ");

System.out.println();

}

// Driver code

public static void main(String args[])

{

int arr[] = { 12, 11, 13, 5, 6, 7 };

System.out.println("Given Array");

printArray(arr);

MergeSort ob = new MergeSort();

ob.sort(arr, 0, arr.length - 1);

System.out.println(" Sorted array");

printArray(arr);

}

}