代码

#include <bits/stdc++.h>
using namespace std;


mt19937 rnd(123);
int rand_int(int low, int high) {
	return low + rnd() % (high - low + 1);
}

const int N = 1e7 + 123;
void insertion_sort(int a[], int n) { 
	for (int i = 1; i < n; ++i) {
		int key = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > key) {
			a[j + 1] = a[j];
			--j;
		}
		a[j + 1] = key;
	}
}

void merge(int a[], int low, int high) {
	static int t[N];
	if (low < high) {
		int mid = low + (high - low) / 2;
		merge(a, low, mid);
		merge(a, mid + 1, high);
		int p = low, q = mid + 1, s = low;
		while (p <= mid && q <= high) {
			t[s++] = a[p] < a[q] ? a[p++] : a[q++];
		}
		while (p <= mid || q <= high) {
			t[s++] = p <= mid ? a[p++] : a[q++];
		}
		for (int i = low; i <= high; i++) a[i] = t[i];
	}
}

void merge_sort(int a[], int n) {
	merge(a, 0, n - 1);
}


void quick_sort(int a[], int n) {
	if (n <= 1) return;
  	const int pivot = a[rand() % n];
	int i = 0, j = 0, k = n;
	while (i < k) {
		if (a[i] < pivot)
			swap(a[i++], a[j++]);
    	else if (pivot < a[i])
			swap(a[i], a[--k]);
		else
			i++;
	}
	quick_sort(a, j);
	quick_sort(a + k, n - k);
}

void intro_sort(int a[], int n) {
	sort(a, a + n);
}

int n = 10000;
int DD = 10000;
int a[N], b[N], c[N];

void check(void (* Sort)(int*, int), const char msg[]) {
	for (int i = 0; i < max(n, DD); i++) a[i] = b[i];

	//chrono::high_resolution_clock cl;
	auto st = cl.now();
	for (int i = 0; i < max(n, DD); i += n) {
		Sort(a + i, n);
	}
	//cout << msg << ":\t" << (cl.now() - st).count() / 1000000. << "ms" << endl;
	for (int i = 0; i < n; i++) assert(a[i] == c[i]);
}


void vain(void (* Sort)(int*, int)) {
	for (int i = 0; i < max(n, DD); i++) a[i] = b[i];
	for (int i = 0; i < max(n, DD); i += n) {
		Sort(a + i, n);
	}
}


#define check(x) check(x, #x)
int main() {
	int nn[] = {10, 100, 1000, 100000, 1000000, 10000000};
	for (auto k : nn) {
		n = k;
		cout << "n = " << n << endl;
		for (int i = 0; i < max(n, DD); i++) a[i] = b[i] = c[i] = rnd();
	
		sort(c, c + n);
	
		vain(intro_sort);
		if (k <= 100000) check(insertion_sort);
		vain(intro_sort);
		check(merge_sort);
		vain(intro_sort);
		check(quick_sort);
		vain(intro_sort);
		check(intro_sort);
	}
	
}

评测结果