MyBlockQuicksort2, C (clang)

Language: Layout:

// http://drops.dagstuhl.de/opus/volltexte/2016/6389/pdf/LIPIcs-ESA-2016-38.pdf

// https://easylang.online/blog/qsort_c.html

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <sys/time.h>

#define LOWER(a, b) ((a) < (b))
#define TYPE int

#define swap(a, b) do { TYPE h = a; a = b; b = h; } while (0)

void small_sort(TYPE* left, TYPE* right) {

// put minimum to left position, so we can save
	// one inner loop comparsion for insert sort
	for (TYPE* pi = left + 1; pi <= right; pi++) {
		if (LOWER(*pi, *left)) {
			swap(*pi, *left);
		}
	}
	for (TYPE* pi = left + 2; pi <= right; pi++) {
		TYPE h = *pi;
		TYPE* pj = pi - 1;
		while (LOWER(h, *pj)) {
			*(pj + 1) = *pj;
			pj -= 1;
		}
		*(pj + 1) = h;
	}
}

#define sort3fast(a, b, c)					\
	if (LOWER(b, a)) {						\
		if (LOWER(c, a)) {					\
			if (LOWER(c, b)) {swap(a, c); } \
			else { 							\
				TYPE h = a; a = b; b = c; c = h;\
			}							\
		} 								\
		else { swap(a, b); }			\
	} 									\
	else {								\
		if (LOWER(c, b)) {				\
			if (LOWER(c, a)) {			\
				TYPE h = c; c = b; b = a; a = h;\
			}							\
			else { swap(b, c); }		\
		}								\
	}									\

#define BSZ 256
#define BSZ 128
TYPE* partition(TYPE* left, TYPE* right) {

TYPE* left_piv = left + 1;
	TYPE* p = left + (right - left) / 2;

TYPE pivl = *left;
	TYPE piv = *p;
	TYPE pivr = *right;
	*p = *left_piv;

sort3fast(pivl, piv, pivr);

*right = pivr;
	*left_piv = piv;
	*left = pivl;
	left += 1;

if (right - left > 2 * BSZ + 2) {
		left += 1;
		right -= 1;
		TYPE* offl[BSZ];
		TYPE* offr[BSZ];
		TYPE** ol = offl;
		TYPE** or = offr;
		do {
			if (ol == offl) {
				TYPE* pd = left;
				do {
					*ol = pd;
					ol += LOWER(piv, *pd);
					pd += 1;
				}
				while (pd < left + BSZ);
			}
			if (or == offr) {
				TYPE* pd = right;
				do {
					*or = pd;
					or += LOWER(*pd, piv);
					pd -= 1;
				}
				while (pd > right - BSZ);
			}

int min = (ol - offl < or - offr) ? ol - offl : or - offr;

ol -= min;
			or -= min;

for (int i = 0; i < min; i++) {
				swap(**(ol + i), **(or + i));
			}
			if (ol == offl) left += BSZ;
			if (or == offr) right -= BSZ;
		}
		while (right - left > 2 * BSZ);

left -= 1;
		right += 1;
	}

while (1) {
		do left += 1; while (LOWER(*left, piv));
		do right -= 1; while (LOWER(piv, *right));
		if (left >= right) break;
		swap(*left, *right);
	}

*left_piv = *right;
	*right = piv;
	return right;
}

void sort(TYPE* data, int len) {

TYPE* stack[64];	// for 2^32 items
	int sp = 0;
	TYPE* left = data;
	TYPE* right = data + len - 1;

while (1) {
		// for arrays smaller than 40 use insert sort 
		if (right - left < 40) {
			small_sort(left, right);
			if (sp == 0) break;
			sp -= 2;
			left = stack[sp];
			right = stack[sp + 1];
		}
		else {
			TYPE* mid = partition(left,right);
			if (mid < left + (right - left) / 2) {
				stack[sp] = mid + 1;
				stack[sp + 1] = right;
				right = mid - 1;
			}
			else {
				stack[sp] = left;
				stack[sp + 1] = mid - 1;
				left = mid + 1;
			}
			sp += 2;
		}
	}
}

double t(void) {
	static double t0;
	struct timeval tv;
	gettimeofday(&tv, NULL);
	double h = t0;
	t0 = tv.tv_sec + tv.tv_usec / 1000000.0;
	return t0 - h;
}

void init(TYPE* data, int len) {
	for (int i = 0; i < len; i++) {
		data[i] = rand();
	}
}

void test(TYPE* data, int len) {
	for (int i = 1; i < len; i++) {
		if (data[i] < data[i - 1]) {
			printf("ERROR\n");
			break;
		}
	}
}

#define SIZE (20 * 1000000)

TYPE data[SIZE];

int main(void) {

init(data, SIZE);
	printf("Sorting %d million numbers with block quicksort ...\n",
		SIZE / 1000000);
	t();
	sort(data, SIZE);
	printf("%.3fs\n", t());
	test(data, SIZE);
	return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.22 sec, absolute running time: 3.62 sec, cpu time: 5.22 sec, memory peak: 192 Mb, absolute service time: 4,06 sec