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.

#include <stdlib.h>
 
int pigeonhole_sort (
  int a[], int n,  /* Array and size of the array */
  int lo, int hi ) /* The range of values stored */
{
  int *buckets = malloc ( ( hi - lo ) * sizeof *buckets );
  int i, j, k;
 
  if ( buckets == NULL )
    return 0;
 
  /* Clear all counts */
  for ( i = 0; i < ( hi - lo ); i++ )
    buckets[i] = 0;
 
  /* Count the number of occurrences for each value */
  for ( i = 0; i < n; i++ )
    buckets[a[i] - lo] = buckets[a[i] - lo] + 1;
 
  k = 0;
 
  /* Copy non-empty buckets back to the array */
  for ( i = 0; i < ( hi - lo ); i++ ) {
    /* Repeat the value as necessary */
    for ( j = 0; j < buckets[i]; j++ )
      a[k++] = i + lo;
  }
 
  return 1;
}