#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <stdbool.h>

typedef enum {
	FIRST, MID, LAST
} PivTp;

void insertionSort(int arr[], int l, int r) {
	int i, key, j;
	for (i = l + 1; i <= r; i++) {
		key = arr[i];
		j = i - 1;

		while (j >= l && arr[j] > key) {
			arr[j + 1] = arr[j];
			j = j - 1;
		}
		arr[j + 1] = key;
	}
}

void quickSort(int v[], int l, int r, int lim, int pivTp)
{
	if (l < r) {
		int m = (l + r) / 2;
		int piv;
		if (pivTp == FIRST) {
			piv = l;
		} else if (pivTp == LAST) {
			piv = r;
		} else {
			piv = (l + r) / 2;
		}
		int aux = v[l];
		v[l] = v[m];
		v[m] = aux;
		int i = l, j = r, d = 0;
		while (i < j) {
			if (v[i] > v[j]) {
				aux = v[i];
				v[i] = v[j];
				v[j] = aux;
				d = 1 - d;
			}
			i += d;
			j -= 1 - d;
		}
		if (i - 1 - l >= lim) {
			quickSort(v, l, i - 1, lim, rand() % 3);
		} else {
			insertionSort(v, l, i - 1);
		}
		if (r - i - 1 >= lim) {
			quickSort(v, i + 1, r, lim, rand() % 3);
		} else {
			insertionSort(v, i + 1, r);
		}
	}
}

#define NMAX 10000000
int main(void)
{
	srand(time(NULL));
	static int arr[NMAX];
	for (int i = 0; i < NMAX; i++) {
		arr[i] = rand() % 100000;
	}
	quickSort(arr, 0, NMAX, 100, rand() % 3);
	for (int i = 1; i < NMAX; i++) {
		assert(arr[i - 1] <= arr[i]);
	}
	return 0;
}