#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

void
pigeonholesort(int arr[], int size)
{
  int  i     = 0;
  int  j     = 0;
  int  min   = arr[0];
  int  max   = arr[0];
  int  range = 0;
  int *holes = NULL;
	
  /* Get the range of the array. */
  for (i = 0; i < size; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  range = max - min + 1;
  
  /* Make some holes and put array numbers in them. */
  holes = (int *)malloc(sizeof(int) * range);
  if (holes == NULL) {
    perror("malloc");
    exit(EXIT_FAILURE);
  }
  
  for (i = 0; i < range; i++) {
    holes[i] = 0;
  }
  
  for (i = 0; i < size; i++) {
    holes[arr[i] - min]++;
  }
  
  /* Copy the numbers back to the original array. */
  j = 0;
  for (j = 0, i = 0; i < range; i++) {
    while (holes[i] > 0) {
      arr[j] = i + min;
      holes[i]--;
      j++;
    }
  }
  
  free(holes);
}

int
main(void)
{
  int  i   = 0;
  int  n   = 0;
  int *arr = NULL;
  
  printf("Enter the size of the array: ");
  scanf("%d", &n);
  
  arr = (int *)malloc(sizeof(int) * n);
  if (arr == NULL) {
    perror("malloc");
    exit(EXIT_FAILURE);
  }
  
  printf("You entered: ");
  for (i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  
  pigeonholesort(arr, n);
  
  printf("Sorted array: ");
  for (i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  
  free(err);
  
  return EXIT_SUCCESS;
}