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

int *genArray ( int n, int k )
{
   int *A, i;

   A = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      A[i] = rand() % (k+1);
      if (rand() % 2) A[i] = -A[i];
   }

   return A;
}

void prnArray ( int *A, int n )
{
   int i;
   for (i=0; i<n; ++i) {
      printf("%5d",A[i]);
      if (i % 16 == 15) printf("\n");
   }
   if (i % 16) printf("\n");
}

int *pass1 ( int *A, int n, int k )
{
   int *C, i;

   C = (int *)malloc((2*k + 1) * sizeof(int));
   for (i=0; i<=2*k; ++i) C[i] = 0;
   for (i=0; i<n; ++i) ++C[k+A[i]];

   return C;
}

void accCounts ( int *C, int k )
{
   int i;


   for (i=2*k; i>=1; --i) C[i] = C[i-1];
   C[0] = 0;
   for (i=1; i<=2*k; ++i) C[i] += C[i-1];
}

void pass2 ( int *A, int *C, int n, int k )
{
   int h, i, j, r;

   i = 0;
   while (i < n) {
      r = A[i];                      /* The element to investigate */
      j = C[k+r];                    /* Insertion location for this element */
      h = (r) ? C[k+r-1] : 0;        /* Insertion location of r-1 */
      if ((i >= h) && (i < j)) ++i;  /* Element r is already in place */
      else { A[i] = A[j]; A[j] = r; ++C[k+r]; }
      /* prnArray(A,n); */
   }
}

int main ( int argc, char *argv[] )
{
   int *A, *C, n, k;

   srand((unsigned int)time(NULL));

   if (argc >= 3) { n = atoi(argv[1]); k = atoi(argv[2]); }
   else scanf("%d%d", &n, &k);

   A = genArray(n,k);

   printf("\n+++ The array before sorting\n");
   prnArray(A,n);

   C = pass1(A,n,k);
   accCounts(C,k);
   pass2(A,C,n,k);

   printf("\n+++ The array after sorting\n");
   prnArray(A,n);

   exit(0);
}