Question

write programs of insertion sort, and mergesort. Find the input size n, that mergesort starts to beat insertion sort in terms of the worst-case running time. You can use clock_t function (or other time function for higher precision) to obtain running time. You need to set your input such that it results in the worst-case running time. Report running time of each algorithm for each input size n.

Answer 1

We will be using clock_t function available into ctime header library in c++.clock() time depends on OS that is how OS allocate resources to process and that's why clock() time may be faster or slower than actual clock.

We will implement standard algorithm of merge sort and insertion sort. and will compare time taken by both algorithm.

For worst case input, its clear from algorithm of merge sort that all three cases (best,worst and average) time complexity is same so we just need to look for insertion sort's worst case, which is happened when input is sorted in reverse order. let's take input array as [10000,999,998,...,1] . 10000 to 1

Worst case time complexity for merge sort is O(nlogn)

Worst case time complexity for insertion sort O(n^2)

below is code for comparison. also I put screenshot of code and output. please note that clock time for merge sort is too less so its rounded up equal to zero.

//=====================================================================//

//c++ program for comparison of merge sort and insertion sort
#include <bits/stdc++.h>
using namespace std;

void merge_array(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* creating 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];

/* Merging both temp arrays back into arr[l..r] in increasing order*/
i=0; // Initial index of left subarray
j=0; // Initial index of right subarray
k=l; // Initial index of merged subarray
while(i<n1&&j<n2)
{
if(L[i]<=R[j])
{
arr[k]=L[i];
i++;
}
else
{
arr[k]=R[j];
j++;
}
k++;
}
/* Copy the rest elements*/
while(i<n1)
{
arr[k]=L[i];
i++;
k++;
}
while(j<n2)
{
arr[k]=R[j];
j++;
k++;
}
return ;
}

/*standard implementation of merge sort */
void merge_sort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
// Sort both, first and second halves
merge_sort(arr, l, m);
merge_sort(arr, m+1, r);
merge_array(arr, l, m, r);
}
return ;
}

/*standard implementation of insertion sort */
void insertion_sort(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;
}
return ;
}

int main()
{
int n = 10000; //size of input array
int tmp = 10000;
int arr[n];
/*creating array in decreasing order for worst case */
for(int i=0;i<10000;i++)
{
arr[i] = tmp;
tmp--;
}

clock_t insertion_time_req; //variable to store time required for insertion sort
clock_t merge_time_req; //variable to store time required for merge sort

insertion_time_req = clock();
insertion_sort(arr, n); //calling procedure for insertion sort
insertion_time_req = clock() - insertion_time_req;

/*same array as above */
tmp = 10000;
for(int i=0;i<10000;i++)
{
arr[i] = tmp;
tmp--;
}

merge_time_req = clock();
merge_sort(arr, 0, n-1); //calling procedure for merge sort
merge_time_req = clock() - merge_time_req;
//here we will type cast clock to second
cout << "Processor time taken for insertion sort : " << (float)insertion_time_req/CLOCKS_PER_SEC << " seconds" << endl;
cout << "Processor time taken for merge sort : " << (float)merge_time_req/CLOCKS_PER_SEC << " seconds" << endl;
return 0;
}
//=====================================================================//