stable in-place mergesort

ssort.c

/*
 * ssort.c implements a stable in-place merge sort as described on [1].
 * The crux of the algorithm is that, when merging two adjacent
 * sub-arrays, one needs to find the longest suffix of the first
 * subarray where every element is larger than any element in a prefix
 * of similar length in the second subarray.  Swapping this prefix for
 * the suffix causes every element in the second subarray to be larger
 * than every element in the first subarray, which is half the battle.
 * The rest can be merged by recursing the merge procedure into both
 * subarrays.  The unfortunate consequence of this is that the merge
 * procedure takes O(n log n) time, which makes the entire algorithm
 * O(n log^2 n), but never let it be said that stable in-place merging
 * is both cheap and easy.
 * 
 * To test the algorithm, compile ssort.c with `gcc -o ssort ssort.c`
 * and run the resulting binary like `./ssort <string>...`.
 * 
 * Copyright (c) 2015 Lari Rasku.  This code is released to the public
 * domain, or under CC0 if not applicable.
 * 
 * [1] https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-demystified-2/
 */

#include <stdio.h>
#include <string.h>

void		ssort(void *, size_t, size_t, int (*)(const void *, const void *));
static void	merge(void *, size_t, size_t, size_t, int (*)(const void *, const void *));
static void	memswap(void *, void *, size_t);
static int	strvcmp(const void *, const void *);

/*
 * ssort stably sorts the array of nmemb elements of size size pointed
 * to by base using the total ordering defined by the compar function.
 * compar takes two constant pointers to elements of base as arguments
 * and returns an integer less than, equal to, or greater than zero if
 * the first argument is respectively less than, equal to, or greater
 * than the second.
 */
void
ssort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	size_t	mid = nmemb / 2;
	char	*p = (char *)base + mid * size;
	
	if (nmemb <= 2)
		merge(base, mid, nmemb, size, compar);
	else {
		ssort(base, mid, size, compar);
		ssort(p, nmemb-mid, size, compar);
		merge(base, mid, nmemb, size, compar);
	}
}

/*
 * merge stably merges the two subarrays base[0..mid) and base[mid..len)
 * in-place.  Like in ssort, size denotes the size of an element of base
 * and compar is a comparison function for a pair of such elements.
 */
static void
merge(void *base, size_t mid, size_t len, size_t size, int (*compar)(const void *, const void *))
{
	char	*p = (char *)base + mid * size;
	size_t	w;
	
	if (mid == 0 || mid == len)
		return;
	if (mid == 1) {
		/* insert forward */
		while (mid < len && compar(&p[-size], p) > 0) {
			memswap(&p[-size], p, size);
			p += size;
			mid++;
		}
		return;
	}
	if (len - mid == 1) {
		/* insert backward */
		while (mid > 0 && compar(&p[-size], p) > 0) {
			memswap(&p[-size], p, size);
			p -= size;
			mid--;
		}
		return;
	}
	else {
		/* recursive step */
		for (w = 0; w < mid; w++)
			if (compar(&p[-(w+1)*size], &p[w*size]) <= 0)
				break;
		memswap(&p[-w*size], p, w*size);
		merge(base, mid-w, mid, size, compar);
		merge(p, w, len-mid, size, compar);
	}
}

/*
 * memswaps swaps the size bytes pointed to by a and b.  Behavior is
 * undefined if the size bytes following a and b overlap.
 */
static void
memswap(void *a, void *b, size_t size)
{
	char	*pa = a;
	char	*pb = b;
	char	tmp;
	
	while (size-- > 0) {
		tmp = *pa;
		*pa++ = *pb;
		*pb++ = tmp;
	}
}

/*
 * strvcmp is a simple wrapper for strcmp for use as a comparator
 * function in sorts.
 */
static int
strvcmp(const void *a, const void *b)
{
	const char	* const *pa = a;
	const char	* const *pb = b;
	
	return strcmp(*pa, *pb);
}

/*
 * main takes a list of strings as its argument and prints them sorted
 * in ascending ASCIIbetical order, one per line, to standard output.
 */
int
main(int argc, char *argv[])
{
	size_t	i;
	
	argc--;
	argv++;
	ssort(argv, argc, sizeof *argv, strvcmp);
	for (i = 0; i < argc; i++)
		printf("%s\n", argv[i]);
}