Decided to brush up on my sorting algorithms, and got a little sidetracked writing a memswap() while I was at it.

sorting.c

/*
 * In a recent interview I was asked to write a function to sort an array on the whiteboard. I
 * wrote a simple compare function, included stdlib.h, and called qsort(3). I was told that didn't
 * count and I had to manually sort the array. Seeing as it had been several years since I had
 * done that, it was more challenging than it should have been. After the interview I decided to
 * brush up on my sorting algorithms, which lead to this.
 *
 * The following sorting algorithms are not optimized. They are short and simple, meant purely
 * to refresh my memory and be easy to understand. There are helper functions along the way that
 * take arguments that may not be used, but I have left those in place so I can go back later
 * and add error checking/asserts if I so wish.
 *
 * Enjoy.
 */

#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

/*
 * not safe, but saves declaration and assignment, and I'm using it correctly...for now
 * (4 days from now "ow, what's this hole in my foot?")
 */
#define MIN(x, y) ((x) <= (y) ? (x) : (y))
//#define MIN(x, y) ({ typeof(x) _x = (x), _y = (y); _x <= _y ? _x : _y; })

/*
 * swap two chunks of memory of size 'size' pointed to by 'x' and 'y' one 'type' at a time
 * based on glibc's SWAP for qsort
 * NOTES: I hope/assume the compiler changes the division to a shift because sizeof(type)
 *        should always be a power of 2. How can I go from sizeof() to log2(sizeof()) so I
 *        can make it a shift anyway?
 *        I also assume here that the single divide/shift up front with decrements in the
 *        loop is faster than no divide/shift and doing 'size -= sizeof()' in the loop
 * TODO:  Figure out why glibc uses do while instead of while. Performance? Style?
 */
#define SWAP(type, x, y, size) ({                  \
    register size_t _size = (size) / sizeof(type); \
    register type *_x = (type *)(x);               \
    register type *_y = (type *)(y);               \
    while (_size-- > 0) {                          \
        type _t = *_x;                             \
        *_x++ = *_y;                               \
        *_y++ = _t;                                \
    }                                              \
})

#define SWAP_BYTEWISE(x, y, size) SWAP(char     , x, y, size)
#define SWAP_WORDWISE(x, y, size) SWAP(uintptr_t, x, y, size)

/*
 * find nearest word aligned address, and how far we are from it
 * do this both in the forward and backward directions
 * NOTE: assuming uintptr_t is word sized. Is this a good assumption?
 */
#define ALIGN(x)  ((uintptr_t)((x) + sizeof(uintptr_t) - 1) & ~(sizeof(uintptr_t) - 1))
#define OFFSET(x) (ALIGN(x) - (uintptr_t)(x))

#define ALIGN_BACK(x)  ((uintptr_t)(x) & ~(sizeof(uintptr_t) - 1))
#define OFFSET_BACK(x) ((uintptr_t)(x) - (ALIGN_BACK(x)))

/*
 * perform the swaps a word at a time when possible, taking care of leading and trailing bytes
 * when is it better to just use a big temporary buffer and memcpy around for the swap?
 * NOTES: I felt it was too big to be a macro, but is called often enough that it should be inline,
 *        is that a good idea or a bad idea? In its current form, memswap causes my quicksort to be
 *        faster than glibc's qsort under specific circumstances. e.g. large array of unsigned long long
 *        and compiled with -O3 (very specific circumstances...).
 * TODO:  figure out if it's better to have an 'else' clause, or to set x, y, and size to leftovers
 *        and have a bytewise swap outside the if that takes care of innequal offsets and leftovers.
 *        Compile glibc's qsort with their SWAP() and this memswap and compare
 *        Figure out if this is faster due to word boundaries, or just because it's swaping 8 times as
 *        much every time
 *        If the offsets are not equal, could I still do this by reading/masking/writing out of phase?
 */
inline void memswap(char *x, char *y, size_t size)
{
	size_t xoff = OFFSET(x);

	if (xoff == OFFSET(y)) { // if x and y have the same offset from word alignment
		SWAP_BYTEWISE(x                   , y                   , xoff                 );
		SWAP_WORDWISE(x + xoff            , y + xoff            , size - xoff          );
		SWAP_BYTEWISE(ALIGN_BACK(x + size), ALIGN_BACK(y + size), OFFSET_BACK(x + size));
	} else {
		SWAP_BYTEWISE(x, y, size);
	}
}

/*
 * macro to define comparison functions for native types
 */
#define CMP_FUNC(name, type)            \
int name(const void *a, const void *b)  \
{                                       \
    const type *_a = (const type *)a;   \
    const type *_b = (const type *)b;   \
    return ((*_a > *_b) - (*_b > *_a)); \
}

CMP_FUNC( char_cmp, char              )
CMP_FUNC(short_cmp, short             )
CMP_FUNC(  int_cmp, int               )
CMP_FUNC(  ull_cmp, unsigned long long)

/*
 * macro to define print functions for native types
 */
#define PRINT_FUNC(name, type, conv) void name(const void *a) { printf("%" conv " ", *(type*)a); }

PRINT_FUNC(print_char , char              , "hhd")
PRINT_FUNC(print_short, short             , "hd" )
PRINT_FUNC(print_int  , int               , "d"  )
PRINT_FUNC(print_ull  , unsigned long long, "llu")

/*
 * print an array using 'print' on each element
 */
void print_array(void *base, size_t nmemb, size_t size, void (*print)(const void *))
{
	char *p, *end;

	for(p = (char*)base, end = p + nmemb * size; p < end; p+= size)
		print((void*)p);
}

/*
 * shuffle an arary
 */
void shuffle(void *base, size_t nmemb, size_t size)
{
	size_t i;
	char *pbase = (char *) base;

	for (i = nmemb - 1; i > 0; i--)
		memswap(pbase + i * size, pbase + (random() % (i + 1)) * size, size);
}

/*
 * check if an array is sorted
 */
int is_sorted(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	char *p = (char *)base, *end = p + nmemb * size;

	for (p += size; p < end && compar((void*)p - size, (void*)p) <= 0; p += size)
		;

	return (p == end);
}

/*
 * check if an array is a heap using 'compar' to compare elements
 */
int is_heap(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	char *pbase = (char *)base;
	size_t i;

	for (i = 1; i < nmemb && compar((void*)(pbase + i * size), (void*)(pbase + (i - 1) / 2 * size)) <= 0; i++)
		;

	return (i == nmemb);
}

/*
 * sorting algorithms
 */

/*
 * bubble sort: let's make some computer scientists cry
 * repeatedly step through array, swapping adjacent elements if they are out of order
 * after each pass one more element at the end of the array is quaranteed to be in place
 */
void bubble_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	char *left, *right, *pbase = (char *)base;

	for (right = pbase + nmemb * size - size; right > pbase; right -= size)
		for (left = pbase; left < right; left += size)
			if (compar((void*)left, (void*)right) > 0)
				memswap(left, right, size);
}

/*
 * insertion sort: for each element (starting with the second), copy it, move backwards
 * through the array shifting up each element we pass and then insert the current element
 * into the correct place
 */
void insert_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	char *p, *ins, tmp[size], *pbase = (char *)base, *end = pbase + size * nmemb;

	for (p = pbase + size; p < end; p += size) {
		memcpy(tmp, p, size);
		for (ins = p - size; ins >= pbase && compar((void*)ins, (void*)tmp) > 0; ins -= size)
			memcpy(ins + size, ins, size);
		memcpy(ins + size, tmp, size);
	}
}

/*
 * selection sort: loop through the array to find the minimum element, then swap it with the
 * leftmost unsorted element.
 */
void select_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	char *left, *right, *min, *pbase = (char *)base, *end = pbase + size * nmemb;

	for (left = pbase; left < end; left += size) {
		for (min = right = left; right < end; right += size)
			if (compar((void*)right, (void*)min) < 0)
				min = right;
		memswap(min, left, size);
	}
}

/*
 * bogo sort: this one's worse than bubble sort. More of a joke, it was too easy to leave out.
 * while the array isn't sorted, shuffle and try again
 */
void bogo_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	while(!is_sorted(base, nmemb, size, compar))
		shuffle(base, nmemb, size);
}

/*
 * sift down: move an element down a heap until it is correctly place
 */
void sift_down(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t top, size_t bottom)
{
	char *pbase = (char *)base;
	size_t child;

	for (; top * 2 + 1 <= bottom; top = child) {
		child = top * 2 + 1;
		if (child + 1 <= bottom && compar((void*)(pbase + child * size), (void*)(pbase + (child + 1) * size)) < 0)
			child++;
		if (compar((void*)(pbase + child * size), (void*)(pbase + top * size)) < 0)
			return;
		memswap(pbase + child * size, pbase + top * size, size);
	}
}

/*
 * sift_up: move an element up a heap until it is correctly placed
 */
void sift_up(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t top, size_t bottom)
{
	char *pbase = (char *)base;
	size_t child, parent;

	for (child = bottom; child > top; child = parent) {
		parent = (child - 1) / 2;
		if (compar((void*)(pbase + parent * size), (void*)(pbase + child * size)) < 0)
			memswap(pbase + parent * size, pbase + child * size, size);
		else
			return;
	}
}

/*
 * heapify: given an array, shift elements around to satisfy the heap condition
 * NOTE: it's possible to do this with sift_up or sift_down. According to wikipedia (and I think
 *       I understand) sift_down gives O(n) time and sift_up gives O(nlogn) time.
 */
void heapify(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	/*
	size_t bottom;

	for (bottom = 1; bottom < nmemb; bottom++)
		sift_up(base, nmemb, size, compar, 0, bottom);
	*/
	int top;

	for (top = (nmemb - 2) / 2; top >= 0; top--)
		sift_down(base, nmemb, size, compar, top, nmemb - 1);
}

/*
 * heap sort: heapify the array, then repeatedly swap the max element (array[0] due to the heap)
 * into the correct place at the end of the unsorted array, and restore the heap condition by
 * sifting down the element now in array[0]
 */
void heap_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	char *pbase = (char *)base;
	int bottom;

	heapify(base, nmemb, size, compar);

	for (bottom = nmemb - 1; bottom > 0; sift_down(base, nmemb, size, compar, 0, --bottom))
		memswap(pbase, pbase + bottom * size, size);
}

/*
 * merge: two sorted lists, both stored in 'base', starting at indices 'left' and 'right, will be
 * merged in sorted order and placed into 'merged' starting at index 'left'
 */
void merge(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t left, size_t right, size_t end, void *merged)
{
	char *pbase = (char *)base;
	size_t m, i = left, j = right; // index into merged, left, and right respectively

	for (m = left; m < end; m++)
		if (i < right && (j >= end || compar((void*)(pbase + i * size), (void*)(pbase + j * size)) <= 0))
			memcpy(merged + m * size, pbase + i++ * size, size);
		else
			memcpy(merged + m * size, pbase + j++ * size, size);
}

/*
 * merge sort: starting with n lists of size 1, lists are merged in pairs, halving the number of
 * lists and doubling the size. A bottom up approach to merge sort that avoids recursion.
 * NOTE: A buffer of the same size as the array being sorted must be supplied. This is used to merge
 *       into each time.
 *       Interesting tidbit, this merge_sort uses the exact same number of compares as glibc's qsort
 */
void merge_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), void *buf)
{
	char *pbase = (char *)base, *pbuf = (char *)buf;
	size_t width, i, nswaps = 0;

	for (width = 1; width < nmemb; width *= 2) {
		for (i = 0; i < nmemb; i += 2 * width)
			merge(pbase, nmemb, size, compar, i, MIN(i + width, nmemb), MIN(i + 2 * width, nmemb), pbuf);
		memswap((char*)&pbase, (char*)&pbuf, sizeof(pbase));
		nswaps = !nswaps;
	}
	if (nswaps) // final list is in buf, copy it to base
		memcpy(base, buf, nmemb * size);
}

/*
 * partition: partitions an array for use with quicksort, using the last element as the pivot.
 * all elements less than and greater than the pivot come before and after the pivot respectively
 * return a pointer to the pivot
 */
char *partition(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), char *low, char *high)
{
	char *p;

	for (p = low; p < high; p += size) {
		if (compar((void*)p, (void*)high) < 0) {
			memswap(p, low, size);
			low += size;
		}
	}
	memswap(low, high, size);
	return low;
}

/*
 * these macros are taken from glibc's qsort.c
 * they implement a fast and simple stack for use with quicksort in order to avoid recursion
 * as long as the smaller of the two partitions is sorted first, the stack will never grow larger
 * than log(n). for 32 bit machines this is 32 entries (64 on 64 bit machines). instead of calculating
 * just use that size, comes out to 256 bytes on 32 bit machines and 1024 on 64 bit
 * NOTE: these aren't pretty, and aren't very safe, don't use them outside of quick_sort please
 */
#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
#define PUSH(lo, hi) ((void) ((top->low = (lo)), (top->high = (hi)), top++))
#define POP(lo, hi)  ((void) (top--, ((lo) = top->low), ((hi) = top->high)))
#define STACK_NOT_EMPTY (stack < top)
struct stack_node {
	char *low, *high;
};

/*
 * quick sort: parition the array, push the larger partition, push the smaller partition, repeat
 */
void quick_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
	struct stack_node stack[STACK_SIZE];
	struct stack_node *top = stack;
	char *low, *mid, *high, *pbase = (char *)base;

	PUSH(pbase, pbase + (nmemb - 1) * size);

	while(STACK_NOT_EMPTY) {
		POP(low, high);

		mid = partition(base, nmemb, size, compar, low, high);

		if (mid - low > high - mid) {
			if (mid - size > low)  PUSH(low, mid - size);
			if (mid + size < high) PUSH(mid + size, high);
		} else {
			if (mid + size < high) PUSH(mid + size, high);
			if (mid - size > low)  PUSH(low, mid - size);
		}
	}
}


/*
 * easily change the data type I'm testing with
 */
void no_print(const void *a) {}
#define TYPE  unsigned long long
#define CMP   ull_cmp
#define PRINT no_print

/*
 * test all the sorting algorithms. on data sets large enough to see the difference between the fast algorithms
 * the slow ones just take way too long.
 *
 * TODO: test with big structures, something multiple words in length, and compare different swap techniques
 */
int main()
{
	int i, len = 1024 * 1024 * 8;
	TYPE *a, *b; // b is used as a buffer for merge sort

	if ((a = malloc(len * sizeof(TYPE))) == NULL) { printf("failed to malloc\n"); return 1; }
	if ((b = malloc(len * sizeof(TYPE))) == NULL) { printf("failed to malloc\n"); return 1; }

	/*
	// test unaligned pointers with same offset
	a = (TYPE *)((char *)a + 1);
	b = (TYPE *)((char *)b + 1);

	len--;
	*/

	/*
	// test unaligned pointers with different offset
	a = (TYPE *)((char *)a + 1);
	b = (TYPE *)((char *)b + 2);

	len--;
	*/

	// fill array, with some duplicates
	for (i = 0; i < len; i++)
		a[i] = (random() % 2) ? i : i + 1;

	printf("qsort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	qsort      ((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("merge sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	merge_sort ((void*)a, len, sizeof(*a), CMP, (void*)b); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("quick sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	quick_sort ((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("heapify\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	heapify    ((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_heap  ((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("heap sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	heap_sort  ((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("select sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	select_sort((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("insert sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	insert_sort((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("bubble sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	bubble_sort((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	printf("bogo sort\n");
	shuffle    ((void*)a, len, sizeof(*a));                print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	bogo_sort  ((void*)a, len, sizeof(*a), CMP);           print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
	printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");

	return 0;
}