/**
 * Copyright © 2016-2019 Xavier G. <xavier@kindwolf.org>
 * This work is free. You can redistribute it and/or modify it under the
 * terms of the Do What The Fuck You Want To Public License, Version 2,
 * as published by Sam Hocevar. See the COPYING file for more details.
 */

void array_sort(unsigned int **array, unsigned int count);
#define ARRAY_SORT 1
#include "common.c"

/* Threshold under which Sedgewick's recommendation feels overkill: */
#define TRIVIAL_ARRAY_THRESHOLD 5

/*
 * Implementation of quick sort:
 */
void quick_sort(unsigned int *array, unsigned int start, unsigned int end) {
	unsigned int count;       /* Size of the array being treated. */
	unsigned int a, b, c;     /* Used for the median-of-three computation. */
	unsigned int pivot_value; /* Value used to determine where to split. */
	unsigned int i;           /* Iterator from the start of the array to the pivot index. */
	unsigned int j;           /* Iterator from the end of the array to the pivot index. */
	unsigned int swap;        /* Used to swap values. */

	if (start >= end) return;
	count = end - start + 1;

	/* Pick a pivot value: */
	if (count < TRIVIAL_ARRAY_THRESHOLD) {
		/* Do not bother for really trivial arrays: */
		pivot_value = array[start];
	}
	else {
		/* Otherwise, follow Sedgewick's recommendation of choosing the median
		of the first, middle and last element of the array: */
		a = array[start]; b = array[start + (count / 2)]; c = array[end];
		if ((a >= b && a <= c) || (a >= c && a <= b)) {
			pivot_value = a;
		}
		else if ((b >= a && b <= c) || (b >= c && b <= a)) {
			pivot_value = b;
		}
		else {
			pivot_value = c;
		}
	}

	/* Determine where to split the array, following Hoare's partition scheme: */
	i = start - 1;
	j = end + 1;
	while (1) {
		do { ++ i; } while (array[i] < pivot_value);
		/* array[i] is now larger than or equal to pivot_value despite being on
		the left side of the pivot. */

		do { -- j; } while (array[j] > pivot_value);
		/* array[j] is now less than or equal to pivot_value despite being on
		the right side of the pivot. */

		if (i >= j) {
			/* i and j passed each other: it is time to split the array at index j: */
			break;
		}

		/* Swap array[i] and array[j] to respect the pivot: */
		swap = array[i];
		array[i] = array[j];
		array[j] = swap;
	}

	/* Sort the sub-arrays on each side of the pivot: */
	quick_sort(array, start, j);
	quick_sort(array, j + 1, end);
}

void array_sort(unsigned int **array, unsigned int count) {
	/* Do nothing unless there are at least two items to sort: */
	if (count < 2) return;

	/* Quick sort is an in-place algorithm, i.e. we work directly on the
	provided array: */
	quick_sort(*array, 0, count - 1);
}