/**
 * 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"

/*
 * Implementation of insertion sort:
 */
void array_sort(unsigned int **array, unsigned int count) {
	unsigned int *src;             /* Unsorted, source array. */
	unsigned int i;                /* Index to iterate over the array. */
	int j;                         /* Index for shifts and insertions. */
	unsigned int register value;   /* Value being repositioned. */
	unsigned int insertions;       /* Stats: # of insertions. */
	unsigned int moved_items;      /* Stats: # of moved items. */

	/* Do nothing unless there are at least two items to sort: */
	if (count < 2) return;

	/* Insertion-sort is an in-place algorithm, i.e. we work directly on the
	provided array: */
	src = *array;

	insertions = 0;
	moved_items = 0;
	for (i = 1; i < count; ++ i) {
		value = src[i];
		/* Look back for the position where src[i] ought to be inserted,
		shifting items on the way: */
		for (j = i - 1; j >= 0 && src[j] > value; -- j) {
			src[j + 1] = src[j];
			++ moved_items;
		}
		/* If needed, insert src[i] to its new, correct position: */
		if (j + 1 != i) {
			src[j + 1] = value;
			++ insertions;
		}
	}
	VERBOSE(1, "  Insertion sort: made %u insertions, moved %u items.\n", insertions, moved_items);
}