#include        <stdio.h>

/****Copyright (c) 1997,1998,1999-2002 All rights reserved
 ****A. V. Gerbessiotis and C. J. Siniolakis
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <limits.h>
#define Div2(x)               ((x) >> 1)
#define Times2(x)             ((x) << 1)
#define CDiv(x, y)            (((x) != 0) ? ((((x) - 1)/(y)) + 1) : 0)
#define Mask(x, sbit, nbits)  ((x >> sbit) & ~(UINT_MAX << nbits))
#define MIN(X,Y)              ((X)<(Y)?(X):(Y))

int FLog2 (int x)
{
  register int l ;

  if (x <= 1) return(0);
  else
    {
      l = 0 ;
      while (x = Div2(x)) ++l ;
      return(l);
    }
}

int CLog2 (int x)
{
  register int l ;

  if (x <= 1) return(0);
  else
    {
      --x ; l = 1 ;
      while (x = Div2(x)) ++l ;
      return(l);
    }
}

int Exp2 (int x)
{
  return (int)((unsigned int)(1) << x) ;
}

void sortint_cntparameters ( int           n,
                             unsigned int  mx_int,
                             int          *sbits,
                             int          *nbits )

{
  int tmp ;

  *sbits = CLog2(mx_int) ; *nbits = FLog2(n) ;
  tmp = CDiv(*sbits, *nbits) ; *nbits = CDiv(*sbits, tmp) ;
  if (*nbits >= (*sbits - 1)) *nbits = *sbits ;
}

void sortint_cnt ( unsigned int *src,
                   int             n,
                   unsigned int  mx_int )

{
  int *trg, *cnt ;
  int  lbit, sbits, nbits, rbits ;
  register int i,j, idx,r ;
 
  if ((n <= 1) || (mx_int <= 0)) return ;

  trg= (int *) malloc(n*sizeof(int));
  if (trg == NULL) {
		printf("error: malloc\n");
		exit(123);
	}


  if (n > mx_int)
    {
      r = mx_int + 1 ;
  cnt= (int *) malloc(r*sizeof(int));
  if (cnt == NULL) {
		printf("error: malloc\n");
		exit(123);
	}

      memset(cnt, 0, r * sizeof(int)) ;
      for (j = 0 ; j < n ; ++j)  cnt[src[j]]++ ;
      for (i = 1 ; i < r ; ++i) cnt[i] +=  cnt[i-1] ;
      for (j = n - 1 ; j >= 0 ; --j)
        {
          idx = --cnt[src[j]] ;
          trg[idx] = src[j] ;
        }
      memcpy(src, trg, n * sizeof(int)) ;

      free(cnt) ;
    }
  else
    {
      sortint_cntparameters(n, mx_int, &sbits, &nbits) ;
      rbits = nbits ; r = Exp2(rbits) + 1 ;
  cnt= (int *) malloc(r*sizeof(int));
  if (cnt == NULL) {
		printf("error: malloc\n");
		exit(123);
	}

      for (lbit = 0 ; lbit < sbits ; lbit += rbits)
        {
          rbits = MIN(nbits, sbits - lbit) ; r = Exp2(rbits) + 1 ;

          memset(cnt, 0, r * sizeof(int)) ;
          for (j = 0 ; j < n ; ++j)  cnt[Mask(src[j], lbit, rbits)]++ ;
          for (i = 1 ; i < r ; ++i) cnt[i] +=  cnt[i-1] ;
          for (j = n - 1 ; j >= 0 ; --j)
            {
              idx = --cnt[Mask(src[j], lbit, rbits)] ;
              trg[idx] = src[j] ;
            }

          memcpy(src, trg, n * sizeof(int)) ;
        }

      free(cnt) ;
    }

  free(trg) ;
}

/*
void sortint_cntmx ( unsigned int *src, int n )
{
  sortint_cnt(src, n, 2147483647) ;
}
*/

void sortint_cntmx ( unsigned int   *src, 
                     int           n )


{
  unsigned int *trg ;
  static int    cnt[65536] ;
  int           i, r ;
  int          j, idx ;
  
  if (n <= 1) return ;

  trg= (unsigned int *) malloc(n*sizeof(unsigned int));
  if (trg == NULL) {
		printf("error: malloc\n");
		exit(123);
	}

  r = 65536 ;
  memset(cnt, 0, r * sizeof(int)) ; 
  for (j = 0 ; j < n ; ++j)  cnt[src[j] & 0x0000FFFF]++ ; 
  for (i = 1 ; i < r ; ++i) cnt[i] += cnt[i-1] ;
  for (j = n - 1 ; j >= 0 ; --j)
    {
      idx = --cnt[src[j] & 0x0000FFFF] ; 
      trg[idx] = src[j] ;
    }

  r = 32768 ;
  memset(cnt, 0, r * sizeof(int)) ; 
  for (j = 0 ; j < n ; ++j)  cnt[trg[j] >> 16]++ ;
  for (i = 1 ; i < r ; ++i) cnt[i] += cnt[i-1] ;
  for (j = n - 1 ; j >= 0 ; --j)
    {
      idx = --cnt[trg[j] >> 16] ;
      src[idx] = trg[j] ;
    }

  free( (void *)trg) ;
}



