/**
* file: BARsort.java - ver. June 2007
* A general sorting algorithm for stable sorting of positive and negative integers
*
* Copyright: Arne Maus, Univ of Oslo, arnem@ifi.uio.no
* This code is avaiable on Apache License, Version 2.0 on request to arnem@ifi.uio.no
*************************************************************************************/

class BARsort {
     static int  MAX_NUM_BIT =11;   // largest bit num in sorting digit
     static int  INSERT_MAX = 32;;  // any value below this, use Insertion sort


     public static int [] getBuffer(int len) {
         // get largest possible integer array  <= len
         int [] buf = new int[1];
         while (buf.length < len) {
              try{
                  buf = new int[len];
              } catch (Error o){
                  len = len *7/10;
              }
           }
           return buf;
       } // end getBuffer


     public static void insertSort(int a[],int left, int right) {
           int i,k,t;      ;

           for (k = left ; k < right; k++) {
             if (a[k] > a[k+1]) {
               t = a[k+1];
               i = k;

               while (i >= left && a[i] > t) {
                    a[i+1] = a[i];
                    i--;
               }
               a[i+1] = t;
           }
         }
    } // end insertSort

   /** BAR sort  int a[]. @return a[0..a.lenth-1] stably sorted */
   public int [] sort(int []a)
   { return sort(a,0, a.length-1);
   }

   /** BAR sort  int a[].from left up to incl. right @return a[left..right ] stably sorted */
   public int [] sort(int []a, int left, int right)
   { // Buffered Adaptive Right Radix

      if (right-left+1 <= INSERT_MAX) {
          insertSort(a,left,right);
          return null;
      } else {
        int max = 0,numBit = 1, n = right-left+1;

        // find max value to be sorted (assume positive numbers)
        for (int i = left ; i <= right ; i++)
           if (a[i] > max) max = a[i];

        while (max >= 1<<numBit) numBit++;

        // get buffer

        int [] b = getBuffer(n);

        if (b.length == n) {
        // determine number of digits and if possible equally sized values
        // Large n, reduce bits
        int  bits = Math.min(MAX_NUM_BIT,numBit) ;
        int numDigits = numBit / bits , // number of digits
            rest      = numBit % bits, r = rest ; // To be added
        if (rest > 0 ) numDigits++;


        bits = numBit/numDigits ; // take average num digits
        rest = numBit%numDigits;

        int [] bit = new int[numDigits];
        for (int i = 0;i < numDigits; i++) {
              bit[i] = bits ;
              if (rest-->0) bit[i]++;
         }

         int shift =0;

         // main loop
         for (int bNo = 0; bNo < numDigits; bNo++){
            bits = bit[bNo];
            radixSortOneDigit(a,b,left,right,bits,shift);
            shift += bits;
         }

       } else  {
            // more than one buffer needed
            sortBAR(a,b, left ,right,numBit);
       }
       return a;
      }
   }


   /** BARsort with more than one buffer */
   static void sortBAR (int[] a, int [] buf, int left, int right, int leftBitNo) {
       // stable sort on a[left..right] - i.e. neg num in top of array
       int len = right-left+1;
       int bits  ;
       int bitLen ;
       int pLen,pStartLen =0; // pLen = at most
       int mask1 ;  // all = 1 in relevant part
       int shift =0 ;

       if(len >1) {

           if (buf!= null && buf.length >0 )
               pStartLen = Math.min (len,buf.length);
           else {
                buf =new int[0];

                pStartLen = len;

                buf = getBuffer(pStartLen);
                pStartLen = buf.length;

               //find buffer
           }

            while (leftBitNo > 0) {
            // Main loop - one more digit to sort on stable wise

                bits = Math.min(MAX_NUM_BIT,leftBitNo); // last digit

                // adjust to sparse distributtions and small numbers
                while( (1<<(bits-1)) > len )  // len > INSERT_MAX > 2**3
                   bits --;

                // previous digit might have reduced pLen, reset
                pLen =pStartLen;

                bitLen = 1<<bits;
                mask1 = bitLen-1 ;
                int mask = mask1 << shift; // all = 1 in relevant bits

                int [] count = new int [bitLen+1];

                for (int i = left; i <= right; i++)
                count[(a[i]& mask) >> shift]++;

                int add1 = count[0], add2;
                count[0] = left; // start  of group 0

                for (int i =0; i < bitLen; i++) {
                    // d)  count [i] points where bundle 'i' starts
                    add2= count[i+1];
                    count[i+1] = count[i] + add1;
                    add1 = add2;
                }

                int numBuffers = (len +pLen-1)/pLen;
                int sorted = left,  // startpos for this digit, a[left ..sorted-1] dealt with
                    ind = 0;

                while (numBuffers-- > 0 ) {
                // inner main loop - one more buffer for this digit

                    pLen = Math.min(pLen,right-sorted+1);  // might in last buffer have less to move
                    // find which indexes to move in this pass
                    int  num = pLen;

                    while ( pLen+sorted > count[ind+1]  ) {
                       ind++;
                    }

                    num = pLen + sorted-count[ind];
                    int nMoved =0, movePos;

                    // a) Move to buffer relvant elements
                    for (movePos = sorted; nMoved < pLen ; movePos++) {
                        // another element in buffer - sort to buffered.
                        int k = (a[movePos]& mask) >> shift;

                        if (k < ind || (k==ind && num-- >0) ) {
                           int to = (count[k]++)-sorted;
                           buf[to] = a[movePos];
                           a[movePos]=-1; // flag for move
                           nMoved++;
                        }
                    } // end sort to buffer

                    // b) move (shift) down other element
                    int from = movePos-2,
                         to   = movePos-1,
                         moveLim =sorted+pLen;

                    while (to >= moveLim ) {
                    // more to shift
                        if(a[from] != -1) {
                            a[to]=a[from];
                            to--;
                        }
                        from--;
                    }

                    // c) move back from buffer to a[]
                    to= sorted;
                    for (int i = 0; i<pLen; i++)
                        a[to++] = buf[i];

                    sorted += pLen; // more sorted
                } // end one buffer

               leftBitNo -= bits;
               shift += bits;

          } // end leftBitNo > 0 - main loop
       }

   } // end BRsort (without perm)


    static int[] radixSortOneDigit ( int [] a, int [] b ,int left, int right, int maskLen, int shift)
         {   int  acumVal = 0, j, n = right-left+1;
             int mask = (1<<maskLen) -1;
             int [] count = new int [mask+1];

             // count= the frequency of each radix value in a
             for (int i = left; i <=right; i++)
               count[(a[i]>> shift) & mask]++;

             // Add up in 'count' - accumulated values
             for (int i = 0; i <= mask; i++) {
               j = count[i];
               count[i] = acumVal;
               acumVal += j;
             }

             // move numbers sorted a to b
             for (int i = 0; i < n; i++)
                 b[count[(a[i+left]>>shift) & mask]++] = a[i+left];

             // copy back b to a
             for (int i = 0; i < n; i++)
                 a[i+left] = b[i] ;

              return a;
            }/* end radixSortOneDigit */

} // end class BARsort





/**
* Class for trditional Right Radix sorting with 8bit sized bytes */
class RRadix8
{
    /** sort a[0..length-1] */
    static int[] sort(int [] a) {
        return sort(a,0,a.length-1);
    }

    /** sort a[0..length-1] */
    static int[] sort(int [] a, int left, int right)
    { // radixSort: a[left..right] with 8bit byte
      int max = 0,numBit = 1, n = right-left+1;

      for (int i = left ; i <= right ; i++)
                   if (a[i] > max) max = a[i];

      while (max >= 1<<numBit) numBit++;

      int [] b = new int[n];
      int shift = 0;
      int numDigits =0;
      while (shift < numBit) {
          BARsort.radixSortOneDigit( a,b, left, right, 8, shift);
          shift +=8;
          numDigits++;
      }

      return null;
    }

} // end RRadix8