I have managed to concur bubble sort, quick sort and heap sort but I've got stuck on pigeonhole sort. I haven't been able to find much on the internet about it.

I have wrote some code for it but it doesn't seem to work. I was wondering if any of you nice people could point me in the direction of a tutorial or something, even just an example.

What I basically want is to to sort random numbers into order.

I will post my code below so you can point out any of the many errors you will find if you wish too.

Any help at all will be appreciated!

```
void pigeonsort( int max, int random[] , int pigeon[] )
{
typedef struct node
{
int data;
struct node* next;
}NODE;
NODE **hashtable, *temp, *p1, *p2;
int i;
int j;
int hashnum;
int hashed;
float tempdata;
int counter[2] = {0,0};
//Copy random array to new array
memcpy( pigeon, random, (sizeof(int)*max));
hashnum= (int)(max*1.5);
hashtable = (NODE**) malloc(sizeof(NODE*)*hashnum);
for(i = 0; i < hashnum; i++)
{
hashtable[i] = NULL;
}// End of for loop.
for (i = 0; i < max; i++)
{
hashed = (int)((long)pigeon[i]*(long)hashnum/1000);
if (hashtable[hashed]==NULL)
{
counter[0]++;
hashtable[hashed] = (NODE*) malloc(sizeof(NODE));
hashtable[hashed]->data = pigeon[i];
hashtable[hashed]->next=NULL;
} //End of if statement.
else
{
temp = (NODE*)malloc(sizeof(NODE));
p2 = hashtable[hashed];
p1 = p2;
counter[0]++;
if(pigeon[i]<= p2->data)
{
hashtable[hashed] = temp;
temp->data = pigeon[i];
temp->next = p1;
}//End of if statement.
else
{
while(pigeon[i] > p2->data )
{
counter[0]++;
p1 = p2;
p2 = p2->next;
if(p2 == NULL) break;
}// End While loop.
counter[1]++;
p1->next = temp;
temp->data = pigeon[i];
temp->next = p2;
} //End else statement.
} // End outer Else statement.
}//End For loop.
for (i = 0, j = 0; i < hashnum; i++)
{
if(hashtable[i] != NULL)
{
p1 = hashtable[i];
while(p1 != NULL)
{
pigeon[j] = p1->data;
p2 = p1;
p1 = p1->next;
j++;
free(p2);
} //End While loop.
}//End if statement.
}//End For loop.
//Print out unsorted & sorted data
printf(" Unsorted || Sorted\n");
printf("----------||----------\n");
for(i = 0; i < max; i++)
{
printf(" %4d || %4d \n", random[i], pigeon[i]);
}
printf("Press Any Key to Continue");
getch();
free(hashtable);
}//End PigeonHole Sort.
```