The other answers to this question have provided all sorts of wonderfully awful sorting algorithms. But one problem remains: they are all too fast.
At some point in graduate school, Prof. Stuart Kurtz and his fellow students had a competition to come up with the slowest sorting algorithm which still made progress towards the sorted list with each step (ruling out, say, sleeping for a google cycles then running quicksort). He came up with Kurtzsort, with a runtime of O(n!...!) (n factorials). For n=2 this is 2!!=2!=2, so the algorithm is essentially instantaneous. For n=3 this is 3!!!=6!!=720!~2.6e1747, considerably more than the number of elementary particles in the universe.
The idea is simple. To sort a list, you can simply form the list of all permutations of that list, then select the smallest one lexigraphically, which is the sorted list. But how do you find the smallest element? You sort of course! If the original list has length n, Kurtzsort does this recursively to depth n, then steps through the resulting list until the smallest element is found.
And just for the benefit of the OP, I implemented Kurtzsort in C. Note that it requires GCC to compile since I use nested functions.
// kurtzsort.c
// implements O(n!...!) (n factorials) space and time complexity sorting algorithm
// requires GCC to compile
// lists of length 3 require ~2.6e1747 bytes and steps
// good luck testing it
#include <stdlib.h>
#include <stdio.h>
// compares arrays of length len1 and len2 with elements consisting of size bytes, lexigraphically
// each element of the array is compared using the compar function
int lex_compar(void *base1, size_t len1, void *base2, size_t len2, size_t size, int (*compar)(void *, void *)) {
// compare element by element
int comparison;
for (size_t i=0; i<len1 & i<len2; i++) {
comparison = compar(base1 + i * size, base2 + i * size);
if (comparison < 0) {
return -1;
} else if (comparison > 0) {
return 1;
}
}
// if first list is shorter return -1, if longer return 1, else return 0
if (len1 < len2) {
return -1;
} else if (len1 > len2) {
return 1;
} else {
return 0;
}
}
// helper function for all_permutations
// determines the length of the resulting array
size_t factorial(size_t n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
// generates an array of all permutations of a given array
void *all_permutations(char *base, size_t len, size_t size) {
// if len == 1 we are done
if (len == 1) {
return base;
}
char *result = malloc(factorial(len) * len * size);
// recursively generate all permutations of all subarrays of length len - 1
char *intermediate_input = malloc((len - 1) * size), *intermediate_result;
size_t int_result_len = factorial(len - 1);
for (size_t i=0; i<len; i++) {
// get the original array minus the ith element
for (size_t j=0; j<i; j++) {
for (size_t k=0; k<size; k++) {
intermediate_input[j * size + k] = base[j * size + k];
}
}
for (size_t j=i; j<len - 1; j++) {
for (size_t k=0; k<size; k++) {
intermediate_input[j * size + k] = base[(j + 1) * size + k];
}
}
// get all permutations of the subarray
intermediate_result = all_permutations(intermediate_input, len - 1, size);
// for each permutation in intermediate_result add the permutation with the removed element in front to result
for (size_t j=0; j<int_result_len; j++) {
// copy the ith element
for (size_t k=0; k<size; k++) {
result[i * int_result_len * len * size + j * len * size + k] = base[i * size + k];
}
// copy the jth permutation
for (size_t t=0; t<len - 1; t++) {
for (size_t k=0; k<size; k++) {
result[i * int_result_len * len * size + j * len * size + (t + 1) * size + k] = intermediate_result[j * (len - 1) * size + t * size + k];
}
}
}
}
// clean up
// if len == 2 then intermediate_input == intermediate_result == base so don't free them
if (len > 2) {
free(intermediate_input);
free(intermediate_result);
}
return result;
}
// kurtzsort, but with specified depth instead of the length of the list
// helper function for defining true kurtzsort
void *kurtzsort_helper(void *base, size_t len, size_t size, int (*compar)(void *, void *), int depth) {
// generate all permutations of the base array
void *permutations = all_permutations(base, len, size);
size_t num_permutations = factorial(len);
// comparison function for permutations
// partially applied version of lex_compar
// requires GCC to compile
int partial_lex_compar(void *a, void *b) {
return lex_compar(a, len, b, len, size, compar);
}
// if depth == 1, step through permutations to find smallest one lexigraphically
// this is the sorted list
if (depth == 1) {
void *min_permutation = permutations;
for (size_t i=0; i<num_permutations; i++) {
if (partial_lex_compar(min_permutation, permutations + i * len * size) > 0) {
min_permutation = permutations + i * len * size;
}
}
return min_permutation;
}
// else apply kurtzsort recursively to get smallest permutation
void *result = kurtzsort_helper(permutations, num_permutations, len * size, partial_lex_compar, depth - 1);
free(permutations);
return result;
}
// sorts an array starting at base of len elements each consisting of size bytes
// compares elements using the compar function
// same calling convention as qsort
void *kurtzsort(void *base, size_t len, size_t size, int (*compar)(void *, void *)) {
return kurtzsort_helper(base, len, size, compar, len);
}
// compares doubles
int double_compar(void *a, void *b) {
double a_d = *((double *) a), b_d = *((double *) b);
if (a_d < b_d) {
return -1;
} else if (a_d > b_d) {
return 1;
} else {
return 0;
}
}
// kurtzsort specifically for doubles
double *kurtzsort_doubles(double *array, int len) {
return kurtzsort(array, len, sizeof(double), double_compar);
}
// main function
// sorts an array of doubles passed via the command line
int main(int argc, char **argv) {
double *input = malloc(sizeof(double) * (argc - 1));
for (int i=1; i<argc; i++) {
input[i - 1] = atof(argv[i]);
}
double *sorted = kurtzsort_doubles(input, argc - 1);
for (int i=0; i<argc - 1; i++) {
printf("%f ", sorted[i]);
}
printf("\n");
exit(0);
}
