Ex. 1. This is a team homework.

Implement a sorting algorithm that is O(n log₂ n) on average, such as Quicksort, Merge Sort, Heapsort. Your programs will the tested on a number of randomly generated arrays of various sizes (the same arrays for everyone). The fastest algorithm in the entire class turned in on time receives 5 extra credit points. Do not use the function sort from the STL, or any other function from the STL except for the swap if you want.

The main program should do the following, in this order:

• ask the user for the size of the array;
• allocate a dynamic array of the appropriate size;
• input all the elements of the array from the cin (I will use redirection from a file for the test);
• sort the array and time the sorting functions alone (see below);
• output the sorted array;
• output the timing information.

In the test, the integers can be from the entire integer range, even though in the file it looks like the are in the range 0 to 9999.

Timing. Here's some information about timing your sorting function. Note that this might not work just like this on Windows or Mac - you'd have to look for the appropriate header on that system. First, include this header file:

#include <sys/time.h>

struct timeval before, after;
double timing;

gettimeofday(&before, 0);

gettimeofday(&after, 0);
timing = (double) ((double)after.tv_sec +
                   (double)after.tv_usec/(1000*1000)) -
         (double) ((double)before.tv_sec +
                   (double)before.tv_usec/(1000*1000));

Github Project. Create a GitHub project for this assignment and add all the team members as collaborators. Submit a link to the GitHub project to Canvas.

Turn in to Canvas: Submit the link to the GitHub project and the name of the other team members to Canvas.