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 selection Reverse 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) [30 points] In Main read the entries given in a input.txt (one line per entry) - given below- and store them into an array. Make four copies of it. Then, on each copy call selection Reverse Sort, mergeReverseSort. For each of these measure the execution time (how long it took to run the reverse sorting) and display this time. (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 selection Reverse 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) [30 points] In Main read the entries given in a input.txt (one line per entry) - given below- and store them into an array. Make four copies of it. Then, on each copy call selection Reverse Sort, mergeReverseSort. For each of these measure the execution time (how long it took to run the reverse sorting) and display this time