Q1 This file mergesort.cpp contains a recursive sort method.

Apply merge sort to this array: { 9, 6, 7, 4, 8 }

Draw the array after each call of the merge function.

Hint: The first time merge is called, the parameters are l=0, m=0, r=1. After this call, the array is

6, 9, 7, 4, 8

Q2

The code below is selection sort. To make it work, please include (it contains the swap method).

void selectionSort(int arr[], int n) { int i, j, min_idx; // One by one move boundary of unsorted subarray for (i = 0; i < n - 1; i++) { // Find the minimum element in unsorted array min_idx = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first element swap(arr[min_idx], arr[i]); } }

You can fill an array with random integer values like this: for (int i = 0; i < ASIZE; i++) arr[i] = rand();

Test the execution time of merge sort and selection sort using several values for ASIZE.

With Windows 10 Power Shell, you can find out the running time of your program like this:

Measure-Command { Start-Process "C:\pathto\mysort.exe" -Wait | Out-Host }

With OSX, the command is "time".

Example:

ASIZE 100 000, merge sort: 1.06, selection sort: xxxx.

ASIZE 200 000, merge sort: xxxx, selection sort: xxxx.