C++ the sorting.cpp skeleton program is shown below

#include

#include

#include

using namespace std;

long compares; // for counting compares

long swaps; // for counting swaps

bool counted_less(int n1, int n2) {

++compares;

return n1

}

void counted_swap(int& n1, int& n2) {

++swaps;

int t = n1;

n1 = n2;

n2 = t;

}

void selectionSort(int* start, int* stop) {

// add code here

}

void insertionSort(int* start, int* stop) {

// add code here

}

void quickSort(int* start, int* stop) {

// add code here

}

void merge(int* start, int* mid, int* stop) {

int temp[stop - start];

int* i = start;

int* j = mid;

int* k = temp;

while (i

if (i == mid) {

counted_swap(*k++, *j++);

} else if (j == stop) {

counted_swap(*k++, *i++);

} else if (counted_less(*j, *i)) {

counted_swap(*k++, *j++);

} else {

counted_swap(*k++, *i++); // bias to left for stability

}

}

for (i = start, k = temp; i != stop; ++i, ++k) {

counted_swap(*i, *k);

}

}

void mergeSort(int* start, int* stop) {

if (stop - start

int* mid = start + (stop-start)/2;

mergeSort(start, mid);

mergeSort(mid, stop);

merge(start, mid, stop);

}

int main(int argc, char** argv) {

string algorithm = "selection sort";

string dataset = "random";

int size = 1000;

for (int c; (c = getopt(argc, argv, "ravmqsi")) != -1;) {

switch(c) {

case 'r': dataset = "random"; break;

case 'a': dataset = "already sorted"; break;

case 'v': dataset = "reversed"; break;

case 'm': algorithm = "merge sort"; break;

case 'q': algorithm = "quicksort"; break;

case 's': algorithm = "selection sort"; break;

case 'i': algorithm = "insertion sort"; break;

}

}

argc -= optind;

argv += optind;

if (argc > 0) size = atoi(argv[0]);

int* data = new int[size];

if (dataset == "already sorted") {

for (int i = 0; i

} else if (dataset == "reversed") {

for (int i = 0; i

} else if (dataset == "random") {

for (int i = 0; i

}

compares = 0;

swaps = 0;

if (algorithm == "merge sort") {

mergeSort(data, data+size);

} else if (algorithm == "quicksort") {

quickSort(data, data+size);

} else if (algorithm == "selection sort") {

selectionSort(data, data+size);

} else if (algorithm == "insertion sort") {

insertionSort(data, data+size);

}

for (int i = 1; i

if (data[i]

cout

exit(1);

}

}

cout

cout

cout

// uncomment for checkpoints 3 and 4

// cout

// cout

}