The goal here is a comparative experimental study, in terms of running time, of the following sorting algorithms.
• Insertion sort.
• Quicksort as shown in exercise above (we will call this algorithm Quick-insertion).
1. Implement these algorithms above within the same program. The input and output are described as follows.
Input: 2 parameters N (number of random naturals to sort) and K (used by Quick-insertion).
Output: Display the list of N randomly generated naturals. For each algorithm display the list of sorted numbers + corresponding running time.
2. Find the pair of values (N, K) where :
(a) Quick-insertion outperforms all the other algorithms.
(b) Insertion sort outperforms all the other algorithms.
(c) Quicksort outperforms all the other algorithms.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.void insertionSort(int data, int n) //Simple insertion sort
for(int i = 1; i < n; i++)
int j = i;
while(j > 0 && data[j-1] > data[j])
int temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
j = j-1;
void mergeSort(int data, int n)
vector<int> dataList; //Used vectors because they're easier to deal with than making several small array
dataList.reserve(n); //Reserve spots to reduce time usage
for(int i = 0;i < n; i++) //Move array into vector
dataList = mergeSortRecursive(dataList); //Run recursive method
for(int i = 0; i < n; i++) //put resulting data vector back into original array
data[i] = dataList[i];