humansort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>

// Sort it like a human!
// O(2n)
void humansort(int **list, int size)
{
    int i, j;
    static short int *sorted = NULL;

    if (!sorted)
        sorted = malloc(INT_MAX);     // should be INT_MAX*sizeof(short int) but....

    memset(sorted,0,size);

    for (i = 0; i < size; i++)
    {
        int x = (*list)[i];
        sorted[x]++;
    }

    for (i = j = 0; i < INT_MAX && j < size; i++)
    {
        while (sorted[i]--)
            (*list)[j++] = i;
    }
}

#ifdef __HUMANSORT_TEST
int main(void)
{
    int *list = malloc(sizeof(int) * 50);

    int i;
    for (i = 0; i < 50; i++)
        list[i] = 50 - i;

    printf("Before: ");
    for (i = 0; i < 50; i++)
        printf("%d ",list[i]);
    putchar('\n');

    humansort(&list,50);

    printf("After: ");
    for (i = 0; i < 50; i++)
        printf("%d ",list[i]);
    putchar('\n');
}
#endif