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

#define min(a, b) ((a < b) ? (a) : (b))

/*
 * Implementation of merge sort:
 */
void array_sort(unsigned int **array, unsigned int count) {
	unsigned int width, i, left_i, right_i, left_end, right_end, j;
	unsigned int *current, *other, *swap;

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

	/* Although in-place (or more precisely, in-place-like) variants exist,
	merge sort is not an in-place algorithm per se. */
	current = *array;
	/* Reserve enough space to copy the whole source array; indeed, merge sort's
	worst case space complexity is O(n). */
	other = malloc(sizeof(unsigned int) * count);

	/* We start with an array of n sorted, 1-item arrays. */
	for (width = 1; width < count; width *= 2) {
		VERBOSE(1, "  Merging pairs of sorted, %u-item(s) arrays, \n", width);
		for (i = 0; i < count; i += 2 * width) {
			left_i    = i;
			right_i   = min(left_i + width,      count - 1);
			left_end  = min(left_i + width - 1,  count - 1);
			right_end = min(right_i + width - 1, count - 1);
			VERBOSE(2, "    Merging [%u-%u] and [%u-%u]\n", left_i, left_end, right_i, right_end);

            /* Spare a few comparisons and assignments if there is only one item: */
            if (left_i == right_end) {
                VERBOSE(3, "      Simply copying [%u] here\n", left_i);
                other[left_i] = current[left_i];
                continue;
            }

            /* Do the same if there is actually only one pair: */
            if (left_end == right_end) {
                VERBOSE(3, "      Simply copying [%u-%u] here\n", left_i, left_end);
                for (j = left_i; j <= left_end; ++ j) {
                    other[j] = current[j];
                }
                continue;
            }

			for (j = left_i; j <= right_end; ++ j) {
				/* Pick from the left array... */
				if (
					left_i <= left_end && /* if still available, and if... */
					(
						right_i > right_end || /* the right one was emptied... */
						current[left_i] <= current[right_i] /* or the left value is smaller. */
					)
				) {
					other[j] = current[left_i];
					++ left_i;
				}
				else {
					other[j] = current[right_i];
					++ right_i;
				}
			}
		}
		/* Swap the roles of our arrays: */
		swap = current;
		current = other;
		other = swap;
	}
    *array = current;
}