Patience Sort

Patience Sort is a sorting algorithm that follows the principle of the card game Patience, also known as Solitaire.

How Patience Sort works

Patience Sort starts by defining what I call the “piles” data structure. It’s basically a 2D array where the rows in the 2nd dimension have variable lengths. These represent piles of sortable elements (in this case, integers) which grow by adding items to the top of them.

The algorithm starts by creating a Piles structure and adding one item to it.

The next item is chosen, placed on top of the first one if it greater, otherwise it is put on a new pile. All the other elements are compared to the top element of all piles and placed where they fit (or a new pile if they fit nowhere).

Once all the elements have been placed in the Piles structure, we’ll have a bunch of sorted sub-arrays. Now it’s time to merge them.

Two piles are picked at a time and the first element of each is compared to each other. The lowest of the two is removed and placed in a new pile. The process is repeated until a pile is emptied (the remaining pile is appended as-is).

This is done with all piles again until only one remains, which ends up being our final sorted array.


In this example, we take an array of the numbers 0-9 and start by placing the first element into a pile.

[5, 0, 8, 9, 7, 2, 6, 4, 1, 3]

Each following element is then either placed on an existing pile if it’s greater or on a new pile if no suitable pile can be found.

[5, 8, 9]
[0, 7]
[2, 6]
[1, 3]

The piles are then merged together by comparing the lowest element in each array.

[0, 5, 7, 8, 9]
[2, 4 ,6]
[1, 3]

And merged again.

[0, 5, 7, 8, 9]
[2, 4 ,6, 1, 3]

And one last time to get a sorted array.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


This is a visualisation of Patience Sort using the piles data structure.

Time complexity

Patience Sort uses comparisons and insertions when adding items to piles and then again when merging back to the array.


Comparisons for Patience Sort are interesting because it’s technically a O(N2) algorithm but it hs such a large shrinking coefficient that it almost feels like O(nlog(n)). Its time complexity is O(n2/200+40n).


Insertions are a bit more standard, looking a more of an O(nlog(n)) kind of time complexity. More specifically, it is O(0.6nlog(n)).


This is how the comparisons and swaps are distributed for this sorting algorithm of size 100 for 100,000 sorts.

Mode: 1074
Mean: 1085
Std dev: 85
Max: 1635

Mode: 400
Mean: 406
Std dev: 15
Max: 485

The comparison distribution for Patience Sort is a normal distribution, but it does seem to have a fixed lower bound and a much more lenient upper bound, making it seem a bit skewed.

The distribution for insertions does seem a lot more unique. There is a huge spike at 400 and then a quick drop to zero followed by a wavy pattern in both directions. I don’t really know how to explain this except that this graph is a sum of various smaller normal distributions all superimposed on one another.

C code

This one is a bit complicated because it relies on the Piles data structure. You can get the full picture here, here and here.

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->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) {
		pile = p->len-1;
	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++) {
		p->piles[i] = NULL;
	p->piles_len = NULL;
	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);
					// 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);
					// 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);
			// 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
		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

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]);

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

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

	// Free the piles


Subscribe to the mailing list

Follow N64 Squid

  • RSS Feed
  • YouTube

Random featured posts