Patience Sort

typedef struct {
	void*** piles;							// Array of piles
	int* piles_len;							// Array holding the length of each pile
	int len;								// Count of piles
	char(**compare_funcs)(void*, void*);		// Functions to be used to compare two elements being pointed to
} piles;

void piles_init(piles* p, char(**compare_funcs)(void*, void*)) {
	p->len = 0;
	p->piles = NULL;
	p->piles_len = NULL;
	p->compare_funcs = compare_funcs;
}

void piles_add_pile(piles* p) {
	// Check to see if there are any existing piles
	p->len++;
	p->piles = realloc(p->piles, p->len * sizeof(void**));
	p->piles[p->len-1] = NULL;
	// Add a new item to length counter and make it zero
	p->piles_len = realloc(p->piles_len, p->len * sizeof(int));
	p->piles_len[p->len-1] = 0;
}

void piles_add_item_to_pile(piles* p, int pile, void* value) {
	if (pile >= p->len || pile < 0) {
		piles_add_pile(p);
		pile = p->len-1;
	}
	p->piles_len[pile]++;
	p->piles[pile] = realloc(p->piles[pile], p->piles_len[pile] * sizeof(void*));
	p->piles[pile][p->piles_len[pile]-1] = value;
}

void piles_clear(piles* p) {
	for (int i=0; i<p->len; i++) {
		free(p->piles[i]);
		p->piles[i] = NULL;
	}
	free(p->piles_len);
	p->piles_len = NULL;
	free(p->piles);
	p->piles = NULL;
}

void piles_merge_to_array(piles* pile, void* a, char size) {
	int i, it;			// Loop iterator
	int i1, i2;			// Pile temp index
	void** temp;		// Temporary array to hold the merging lists
	void* output;
	piles p;

	// Make a copy of the pile
	memcpy(&p, pile, sizeof(piles));
	// Copy the pile lengths
	p.piles_len = malloc(p.len * sizeof(int));
	memcpy(p.piles_len, pile->piles_len, p.len * sizeof(int));
	// Copy the piles
	p.piles = malloc(p.len * sizeof(void**));
	for (i=0; i<p.len; i++) {
		p.piles[i] = malloc(p.piles_len[i] * sizeof(void*));
		memcpy(p.piles[i], pile->piles[i], p.piles_len[i] * sizeof(void*));
	}

	// As long as there is more than one pile
	while(p.len > 1) {

		// Take the first and last pile
		for(i=0; i<p.len/2; i++) {
			i1 = i2 = 0;
			temp = calloc((p.piles_len[i] + p.piles_len[p.len-1-i]), sizeof(void*));
			// Loop through each element on each list
			it = 0; // Index for the temp array
			while (i1 < p.piles_len[i] && i2 < p.piles_len[p.len-1-i]) {

				if ((*p.compare_funcs[COMPARE_LESS_THAN])(p.piles[i][i1], p.piles[p.len-1-i][i2])) {
					// Insert from a1
					memcpy(&temp[it], &p.piles[i][i1], sizeof(void*));
					insert(NULL, 0);
					i1++;
					// Check for end
					if (i1 >= p.piles_len[i]) {
						// Fill in the rest of the array with a2
						for (; i2<p.piles_len[p.len-1-i]; i2++) {
							memcpy(&temp[++it], &p.piles[p.len-1-i][i2], sizeof(void*));
							insert(NULL, 0);
						}
					}
				} else {
					// Insert from a2
					memcpy(&temp[it], &p.piles[p.len-1-i][i2], sizeof(void*));
					insert(NULL, 0);
					i2++;
					// Check for end
					if (i2 >= p.piles_len[p.len-1-i]) {
						// Fill in the rest of the array with a1
						for (; i1<p.piles_len[i]; i1++) {
							memcpy(&temp[++it], &p.piles[i][i1], sizeof(void*));
							insert(NULL, 0);
						}
					}
				}
				it++;
			}
			// Clean things up
			// Increase the size of a1 to accomodate the merge
			p.piles_len[i] += p.piles_len[p.len-1-i];
			p.piles[i] = realloc(p.piles[i], p.piles_len[i] * sizeof(void*));
			// Set the original array to its new values
			memcpy(p.piles[i], temp, p.piles_len[i] * sizeof(void*));
			// Free memory
			free(temp);
			free(p.piles[p.len-1-i]);
		}
		p.len -= p.len/2;
	}

	// Insert into temporary output in the correct order
	output = malloc(p.piles_len[0] * size);
	for (i=0; i<p.piles_len[0]; i++) {
		memcpy(output+(i*size), p.piles[0][i], size);
	}
	// Now copy from output array into the final array
	memcpy(a, output, p.piles_len[0] * size);

	// Free memory
	piles_clear(&p);
	free(output);
}

void patience_sort(int *p, int len) {
	int i, j;		// Loop iterators
	piles stacks;	// Pile object

	// Initialise the piles struct
	piles_init(&stacks, compare_int_funcs);

	// Process first element
	piles_add_item_to_pile(&stacks, 0, &p[0]);

	//Loop through the elements from the source starting from the 2nd one
	for (i=1; i<len; i++) {
		// Loop through piles
		for (j=0; j<stacks.len; j++) {
			if ((*stacks.compare_funcs[COMPARE_GREATER_THAN_EQUAL_TO])(&p[i], stacks.piles[j][stacks.piles_len[j]-1])) {
				// Found a nice pile, add it in
				piles_add_item_to_pile(&stacks, j, &p[i]);
				break;
			}

			if (j == stacks.len-1) {
				// No available pile. Creating new pile...
				piles_add_item_to_pile(&stacks, j+1, &p[i]);
				break;
			}
		}
	}	

	// Convert the piles into a sorted array
	piles_merge_to_array(&stacks, p, sizeof(int));

	// Free the piles
	piles_clear(&stacks);
}