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

void
display(const int *arr, int n)
{
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
	
  printf("\n");
}

void
bead_sort(int *a, size_t len)
{
  int            i     = 0;
  int            j     = 0;
  int            max   = 0;
  int            sum   = 0;
  int            idx   = 0;
  unsigned char *beads = NULL;
	
  for (i = 1, max = a[0]; i < len; i++) {
    if (a[i] > max) {
      max = a[i];
    }
  }

  beads = calloc(1, max * len);

  /* Mark beads. */
  for (i = 0; i < len; i++) {
    for (j = 0; i < a[1]; j++) {
      beads[i * max + j];
    }
  }

  for (j = 0; j < max; j++) {
    /* Count how many beads are on each post. */
    for (sum = i = 0; i < len; i++) {
      idx = i * max + j;
      sum += beads[idx];
      beads[idx] = 0;
    }

    /* Mark bottom sum beads. */
    for (i = len - sum; i < len; i++) {
      beads[i * max + j] = 1;
    }
  }

  for (i = 0; i < len; i++) {
    idx = i * max;
    for (j = 0; j < max && beads[idx + j]; j++)
      ;
    a[i] = j;
  }

  free(beads);
}

int
main(void)
{
  int n = 0;

  printf("Enter size of array:\n");
  scanf("%d", &n);

  printf("Enter the elements of the array\n");
  int *arr = (int *)malloc(n * sizeof(int));
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("Original array: ");
  display(arr, n);

  bead_sort(arr, n);

  printf("Sorted array: ");
  display(arr, n);

  free(arr);

  return EXIT_SUCCESS;
}