# 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.

### Example

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][4][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]`

## Visualisation

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

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)`.

### Inserts

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))`.

### Distribution

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
Min:779

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

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

// 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) {
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

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

if (j == stacks.len-1) {
// No available pile. Creating new pile...
break;
}
}
}

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

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