using System;

using System.Collections.Generic;

using System.Diagnostics;

namespace SimpleSort

{

class Sort

{

static void Main(string[] args)

{

Console.Write(" How many random numbers to you want to sort = ");

string UserInput = Console.ReadLine();

int size = Convert.ToInt32(UserInput);

Random rand = new Random();

int[] A = new int[size];

Console.WriteLine(" Unsorted------------");

//Generate an unsorted array

for (int i = 0; i

{

A[i] = rand.Next(0, 100);

//Console.WriteLine(" " + A[i]);

}

Console.WriteLine(" Built-In Sort------------");

//The built-in "arr.Sort" sorts "in-place",

//i.e. it destroys the original unsorted arr.

//We need to make a temporary copy of the original.

int[] temp = new int[size];

Array.Copy(A, temp, size);

Stopwatch s = new Stopwatch(); // start the stopwatch

s.Start();

Array.Sort(temp);

s.Stop(); //stop the Stopwatch and print the elapsed time

Console.WriteLine(" It took {0} to sort {1} numbers ", s.Elapsed, size);

//for (int i = 0; i

Console.WriteLine(" Mergesort------------");

s.Start();

mergesort(A, 0, size-1);

s.Stop(); //stop the Stopwatch and print the elapsed time

Console.WriteLine(" It took mergesort {0} to sort {1} numbers ", s.Elapsed, size);

//for (int i = 0; i

Console.ReadKey();

}

static void mergesort( int[] A, int l, int r )

{

if (l

{

int midpoint = (l + r)/2; //keep in mind this is integer division

mergesort(A, l, midpoint);

mergesort(A, midpoint+1, r );

merge( A, l, midpoint, r);

}

}

static void merge( int[] A, int l, int midpoint, int r)

// Merges two subarrays of A[].

// First subarray is A[l..m]

// Second subarray is A[m+1..r]

{

int i, j, k;

int n1 = midpoint - l + 1;

int n2 = r - midpoint;

/* create temp arrays */

int[] L = new int[n1];

int[] R = new int[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i

{

L[i] = A[l + i];

}

for (j = 0; j

{

R[j] = A[midpoint + 1 + j];

}

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = l; // Initial index of merged subarray

while (i

{

if (L[i]

{

A[k] = L[i];

i++;

}

else

{

A[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of L[], if there

are any */

while (i

{

A[k] = L[i];

i++;

k++;

}

}

}

}

[10 points] Record the execution times for mergesort and build-in mergesort and graph (in Excel) for the following values of n (250, 500, 1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500). Graph should be clearly labelled. [15 points] Modify the selection sort algorithm seen in class so it works with an array of strings AND the array will have the values sorted in reverse. Also add a local variable count (use long count) of the number of comparisons that were performed. Display it before exiting this method. Call it: static void selectionReverse Sort(string[] arr) [15 points] Modify the merge sort algorithm seen in class so it works with an array of strings AND the array will have the values sorted in reverse. Also add a local variable count (use long count) of the number of comparisons that were performed. Display it before exiting this method. Call it: static void mergeReverse Sort(string[] arr)