C++ std::sort Comparison by James Pate Williams, Jr.

#pragma once
class Sort
{
public:
	void RunSelectionSort(long long* A, int p, int r);
	void RunMergeSort(
		long long* A,
		long long* B,
		long long* C,
		int p, int r);
	void RunQuickSort(long long* A, int p, int r);
private:
	void Merge(
		long long* A,
		long long* B,
		long long* C,
		int p, int q, int r);
	int Partition(long long* A, int lo, int hi);
};

#include <limits.h>
#include "Sort.h"

void Sort::Merge(
    long long* A,
    long long* B,
    long long* C,
    int p, int q, int r)
{
    int n1 = q - p + 1, n2 = r - q;

    for (int i = p, j = 1; i <= q; i++, j++)
        B[j] = A[i];

    for (int i = q + 1, j = 1; i <= r; i++, j++)
        C[j] = A[i];

    B[n1 + 1] = C[n2 + 1] = LLONG_MAX;

    int ii = 1, jj = 1;

    for (int k = p; k <= r; k++)
    {
        if (B[ii] <= C[jj])
        {
            A[k] = B[ii];
            ii++;
        }

        else
        {
            if (B[ii] > C[jj])
            {
                A[k] = C[jj];
                jj++;
            }
        }
    }
}

int Sort::Partition(long long* A, int p, int r)
{
    int q = p;
    long long t;

    for (int u = p; u <= r - 1; u++)
    {
        if (A[u] <= A[r])
        {
            t = A[q];
            A[q]= A[u];
            A[u] = t;
            q++;
        }
    }

    t = A[q];
    A[q] = A[r];
    A[r] = t;

    return q;
}

void Sort::RunMergeSort(
    long long* A,
    long long* B,
    long long* C,
    int p, int r)
{
    int q = (p + r) / 2;

    if (p < r)
    {
        RunMergeSort(A, B, C, p, q);
        RunMergeSort(A, B, C, q + 1, r);
        Merge(A, B, C, p, q, r);
    }
}

void Sort::RunQuickSort(long long* A, int p, int r)
{
    if (p < r)
    {
        int q = Partition(A, p, r);

        RunQuickSort(A, p, q - 1);
        RunQuickSort(A, q + 1, r);
    }
}

void Sort::RunSelectionSort(long long* A, int p, int r)
{
    for (int i = p; i <= r - 1; i++)
    {
        for (int j = i + 1; j <= r; j++)
        {
            if (A[i] > A[j])
            {
                long long t = A[i];

                A[i] = A[j];
                A[j] = t;
            }
        }
    }
}

#include "Sort.h"
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using chrono::duration_cast;
using chrono::milliseconds;

long long A[16], B[18], C[18];
long long AA[100002], BB[100002], CC[100002];

long long RandomLongLong()
{
	long long lo = rand();
	long long hi = rand();

	return (lo << 31) | hi;
}

void GenerateArray(long long A[], int n, int seed)
{
	srand(seed);

	for (int i = 1; i <= n; i++)
		A[i] = RandomLongLong();
}

void GenerateArrayMod(long long A[], int n, int mod, int seed)
{
	srand(seed);

	for (int i = 1; i <= n; i++)
		A[i] = RandomLongLong() % mod;
}

void RunSorts(
	Sort sort,
	long long A[],
	long long B[],
	long long C[],
	int n, int seed)
{
	cout << setw(5) << n << "\t";

	auto start1 = chrono::steady_clock::now();
	sort.RunSelectionSort(A, 1, n);
	auto final1 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<milliseconds>(final1 - start1).count();
	cout << "\t";

	GenerateArray(A, n, seed);

	auto start2 = chrono::steady_clock::now();
	sort.RunMergeSort(A, B, C, 1, n);
	auto final2 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<milliseconds>(final2 - start2).count();
	cout << "\t";

	GenerateArray(A, n, seed);

	auto start3 = chrono::steady_clock::now();
	sort.RunQuickSort(A, 1, n);
	auto final3 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<milliseconds>(final3 - start3).count();
	cout << "\t";

	GenerateArray(A, n, seed);
	vector<long long> V;

	for (int i = 0; i < n; i++)
		V.push_back(A[i + 1]);

	auto start4 = chrono::steady_clock::now();
	std::sort(V.begin(), V.end());
	auto final4 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<milliseconds>(final4 - start4).count();
	cout << endl;
}

void TestSorts(
	Sort sort,
	long long A[],
	long long B[],
	long long C[],
	int n, int seed)
{
	cout << "Testing Sorting Algorthms" << endl;
	cout << "Selection Sort" << endl;

	GenerateArrayMod(A, n, 100000, 1);

	for (int i = 1; i <= n; i++)
		cout << setw(5) << A[i] << " ";

	cout << endl;

	sort.RunSelectionSort(A, 1, n);

	for (int i = 1; i <= n; i++)
		cout << setw(5) << A[i] << " ";

	cout << endl << endl;
	cout << "Merge Sort" << endl;

	GenerateArrayMod(A, n, 100000, 1);

	for (int i = 1; i <= n; i++)
		cout << setw(5) << A[i] << " ";

	cout << endl;

	sort.RunMergeSort(A, B, C, 1, n);

	for (int i = 1; i <= n; i++)
		cout << setw(5) << A[i] << " ";

	cout << endl << endl;
	cout << "Quick Sort" << endl;

	GenerateArrayMod(A, n, 100000, 1);

	for (int i = 1; i <= n; i++)
		cout << setw(5) << A[i] << " ";

	cout << endl;

	sort.RunQuickSort(A, 1, n);

	for (int i = 1; i <= n; i++)
		cout << setw(5) << A[i] << " ";

	cout << endl << endl;
	cout << "std::sort" << endl;

	GenerateArrayMod(A, n, 100000, 1);
	vector<long long> V;

	for (int i = 1; i <= n; i++)
	{
		cout << setw(5) << A[i] << " ";
		V.push_back(A[i]);
	}

	cout << endl;

	std::sort(V.begin(), V.end());

	for (size_t i = 0; i < V.size(); i++)
		cout << setw(5) << V[i] << " ";

	cout << endl << endl;
}

int main(int argc, char** argv)
{
	Sort sort;
	
	TestSorts(sort, A, B, C, 15, 1);

	cout << "Runtimes in Milliseconds" << endl;

	cout << "    n" << "\tSelect" << "\t Merge" << "\t Quick\tstd::sort" << endl;

	for (int n = 10000; n <= 60000; n += 10000)
	{
		RunSorts(sort, AA, BB, CC, n, 1);
	}
	
	return 0;
}