/**
* 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;
}