int insert( input, n, r, A )
dataarray input, r;  int n, *A;

{ extern int m, m2;
  int d, i, ia, ib, iup, j;
  datarecord tempr;

  if( m < n ) return(0);
  for( i=0; i<m2; i++ ) A[i] = 0;
  for( i=0; i<n; i++ ) A[ input[i].k % m2 ]++;
  /* Shellsort input array based on collision counts */
  for ( d=n; d>1; ) {
       if (d<5)  d = 1;
          else   d = (5*d-1)/11;
       for ( i=n-1-d; i>=0; i-- ) {
            tempr = input[i];
            ia = tempr.k % m2;
            for ( j=i+d; j<n && (A[ia] < A[ib=input[j].k % m2] ||
                                 A[ia] == A[ib] && ia > ib); j+=d )
                 input[j-d] = input[j];
            input[j-d] = tempr;
            }
       }

  for( i=0; i<n; i=iup ) {
       ia = input[i].k % m2;
       iup = i + A[ia];
       for( A[ia]=ib=1; ib < 9*m; A[ia] += ib++ ) {
            for( j=i; j<iup && empty(r[hashfunction(A[ia],input[j].k)]);
                 j++ ) r[hashfunction(A[ia],input[j].k)] = input[j];
            if( j >= iup ) break;
            for( j--; j >= i; j-- )
                 r[hashfunction(A[ia],input[j].k)].k = NOKEY;
            }
       if( ib >= 9*m )
           /* Cannot build optimal hashing table with m and m2 */
           return(0);
       }
  return(1);
}