/*
 * This is Vladimir Yaroslavskiy's Dual-Pivot Quicksort
 * See http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
 */

#include	<stdio.h>
#include	"SortLibrary.h"

#ifndef DIST_SIZE
#define DIST_SIZE  13
#endif

#ifndef TINY_SIZE
#define TINY_SIZE  15
#endif

void dualPivotQuicksort(KEY_T a[], int left, int right) {
	int len = right - left;
	KEY_T x;
	KEY_T pivot1, pivot2;
	int i,j,k;
	int less, great;
	int diffPivots;
	int m1, m2, m3, m4, m5;
	int sixth;

	if (len < TINY_SIZE) { // insertion sort on tiny array
		insort(a+left, len+1);
		return;
	}
	// median indexes
	sixth = len / 6;
	m1 = left + sixth;
	m2 = m1 + sixth;
	m3 = m2 + sixth;
	m4 = m3 + sixth;
	m5 = m4 + sixth;
	// 5-element sorting network
	if (a[m1] > a[m2]) { x = a[m1]; a[m1] = a[m2]; a[m2] = x; }
	if (a[m4] > a[m5]) { x = a[m4]; a[m4] = a[m5]; a[m5] = x; }
	if (a[m1] > a[m3]) { x = a[m1]; a[m1] = a[m3]; a[m3] = x; }
	if (a[m2] > a[m3]) { x = a[m2]; a[m2] = a[m3]; a[m3] = x; }
	if (a[m1] > a[m4]) { x = a[m1]; a[m1] = a[m4]; a[m4] = x; }
	if (a[m3] > a[m4]) { x = a[m3]; a[m3] = a[m4]; a[m4] = x; }
	if (a[m2] > a[m5]) { x = a[m2]; a[m2] = a[m5]; a[m5] = x; }
	if (a[m2] > a[m3]) { x = a[m2]; a[m2] = a[m3]; a[m3] = x; }
	if (a[m4] > a[m5]) { x = a[m4]; a[m4] = a[m5]; a[m5] = x; }
	// pivots: [ < pivot1 | pivot1 <= && <= pivot2 | > pivot2 ]
	pivot1 = a[m2];
	pivot2 = a[m4];
	diffPivots = pivot1 != pivot2;
	a[m2] = a[left];
	a[m4] = a[right];
	// center part pointers
	less = left + 1;
	great = right - 1;
	// sorting
	if (diffPivots) {
		for (k = less; k <= great; k++) {
			x = a[k];
			if (x < pivot1) {
				a[k] = a[less];
				a[less++] = x;
			}
			else if (x > pivot2) {
				while (a[great] > pivot2 && k < great) {
					great--;
				}
				a[k] = a[great];
				a[great--] = x;
				x = a[k];
				if (x < pivot1) {
					a[k] = a[less];
					a[less++] = x;
				}
			}
		}
	}
	else {
		for (k = less; k <= great; k++) {
			x = a[k];
			if (x != pivot1) {
				if (x < pivot1) {
					a[k] = a[less];
					a[less++] = x;
				}
				else {
					while (a[great] > pivot2 && k < great) {
						great--;
					}
					a[k] = a[great];
					a[great--] = x;
					x = a[k];
					if (x < pivot1) {
						a[k] = a[less];
						a[less++] = x;
					}
				}
			}
		}
	}
	// swap
	a[left] = a[less - 1];
	a[less - 1] = pivot1;
	a[right] = a[great + 1];
	a[great + 1] = pivot2;
	// left and right parts
	dualPivotQuicksort(a, left, less - 2);
	dualPivotQuicksort(a, great + 2, right);
	// equal elements
	if (great - less > len - DIST_SIZE && diffPivots) {
		for (k = less; k <= great; k++) {
			x = a[k];
			if (x == pivot1) {
				a[k] = a[less];
				a[less++] = x;
			}
			else if (x == pivot2) {
				a[k] = a[great];
				a[great--] = x;
				x = a[k];
				if (x == pivot1) {
					a[k] = a[less];
					a[less++] = x;
				}
			}
		}
	}
	// center part
	if (diffPivots) {
		dualPivotQuicksort(a, less, great);
	}
}