You are given an integer vector which is represented by int* an array of integers and its dimension n as a separate parameter. We are interested in sorting arrays of integer vectors according to a pre-defined notion of vector length. You therefore are given the function ivector_length(v, n) that computes and returns the length of vector v with dimension n a
You are given a naive (and very inefficient) implementation of insertion sort for arrays of integer vectors
Questions
Develop an improved implementation of insertion sort for integer vector (insertion_sort_im) that precomputes the length of each vector before the sorting. Keep in mind that the vectors are sorted according to their length (see ivector_length function). You can test the correctness of your sorting algorithm using the provided check_sorted function.
Implement a merge sort for an array of integer vectors. For this implementation of the merge sort, as is the case for the improved insertion sort algorithm, you should precompute the length of the vectors before the sorting, and the sorting is done according to the vector lengths. Test the correctness of your merge sort implementation using the provided check_sorted function.
Measure the runtime performance of insertion sort (naive and improved) and merge sort for random, sorted, and inverse sorted inputs of size m = 10000; 25000; 50000; 100000; 250000; 500000; 1000000; 2500000 and vector dimension n = 10; 25; 50. You can use the provided functions create_random_ivector, create_sorted_ivector, create reverse_sorted_ivector.
Repeat each test a number of times (usually at least 10 times) and compute the average running time for each combination of algorithm, input, size m, and vector dimension n. Report and comment on your results.
