Merge Sort and Insertion Sort Programs In C++ Implement merge sort and insertion sort to sort an array/vector of integers. Write the code to collect running time data., you will now generate arrays of size n=5,000, 10,000, 15,000, 70,000. containing random integer values from 0 to 10,000 to sort. Output the array size n and time in seconds to the terminal using printf or cout. Name these new programs insertTime.cpp and mergeTime.cpp.

Need the function to show the running time.

Merge Sort

#include

#include

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

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

/* l is for left index and r is right index of the sub-array

of arr to be sorted */

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

{

if (l < r)

{

int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

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

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

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

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

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

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

/* Merge the temp arrays back into arr[l..r]*/

i = 0;

j = 0;

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 the remaining elements of L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

void printArray(int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", A[i]);

printf(" ");

}

Insertion Sort:

#include

#include

#include

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)

{

int i, key, j;

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

{

key = arr[i];

j = i-1;

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

{

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

j = j-1;

}

arr[j+1] = key;

}

}

// A function to print an array of size n

void printArray(int arr[], int n)

{

int i;

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

printf("%d ", arr[i]);

printf(" ");

}