MyBlockQuicksort, C (clang)

MyBlockQuicksort

// 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 insert_sort(TYPE* left, TYPE* right) {
	for (TYPE* pi = left + 1; 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)) swap(a, b);	\
	if (LOWER(c, b)) swap(b, c);	\
	if (LOWER(b, a)) swap(a, b);	\

#define INSERT_SORT_THRE 60
#define BSZ 64

TYPE* xoffl[BSZ + 64];
TYPE* xoffr[BSZ + 64];

TYPE** offl;
TYPE** offr;

TYPE* partition(TYPE* left, TYPE* right) {

TYPE* left_piv = left + 1;
	TYPE* p = left + INSERT_SORT_THRE - 3;

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;
		int offl[BSZ];
		int offr[BSZ];
		int* ol = offl;
		int* or = offr;
		do {
			if (ol == offl) {
				TYPE* pd = left;
				for (int i = 0; i < BSZ;) {
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
					*ol = i++; ol += LOWER(piv, *pd++);
				}
			}
			if (or == offr) {
				TYPE* pd = right;
				for (int i = 0; i < BSZ;) {
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
					*or = i++; or += LOWER(*pd--, piv);
				}
			}

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

for (int i = 0; i < min; i++) {
				ol--; or--;
				swap(left[*ol], right[-(*or)]);
			}
			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) {

offl = (TYPE**)(((long long)xoffl + 63) & ~63);
	offr = (TYPE**)(((long long)xoffr + 63) & ~63);
//	offl = xoffl;
//	offr = xoffr;

TYPE* stack[64];
	int sp = 0;
	TYPE* left = data;
	TYPE* right = data + len - 1;

while (1) {
		if (right - left < INSERT_SORT_THRE) {
			if (left == data) {
				// 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);
					}
				}
				left += 1;
			}
			insert_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: not sorted\n");
			break;
		}
	}
}

#define SIZE (20 * 1000000)

TYPE data[SIZE];

int main(void) {

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


run \| edit \| history \| help	0