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