Advance Algorithm Design

1. Show that

2. Insertion sort/Merge sort

Write a program to implement Insertion sort and Merge sort to sort an array

Input array should be at size of 10, 50, 100, 300, 500, 1000, 2000, 5000, 10000, 50000 for integer numbers that are not sorted at all.

use a pseudo random number generator function to generate an input array

Use any language and environment of your choice, such as C++, Java, or Python. However, C++ and Qt is a recommended choice. If you use Qt, you can use QtChart to draw the graph and compare the execution time for both algorithms.

(x-axis = input size n, and y-axis = the running time (ms))..

Conclude what you observe and justify your answer.

Show that 3n3-2n + 3-6(n*)