// ==============WARNING: Can use up a lot of memory!========================
/*
 * The Good:
 *   Decent speed for large array.
 *   Customizable sort method (I may be the only one that wants this feature :P )
 *   Constant number of passes to sort, regardless of the data inside the array
 * The Bad:
 *   2*n + 1536 bytes memory footprint (and some variables)
 *   Only works with integer arrays, but could probably be made to work with characters in a string
 *   A presorted array takes the same number of steps as an unsorted array
 * The Ugly?:
 *   Using random() to generate the values can take longer than it does to sort them...
 *
 *
 * Click to create and sort an array of int's
 * When sorting 16M ints (4096x4096), if it seems to take a very long time on your machine,
 * try changing w or h  even by one, I have only seen this occasionally, but it seems to make a difference
 * at the 24-32 bit transition. My only guess is that it has something to do with JIT looking for optimization.
 *
 */

int w = 2048, h = 2048; // 4M takes on average a 1/2 second on my machine

PImage out;

int[] datasrc;
int[][] counts = new int[4][256];

void setup() {
  
  size(512,512);
  
  out = createImage(w, h, ARGB);
  
  datasrc = new int[out.pixels.length];
  
  counts = new int[4][256];
  
  noLoop();
}


void mouseClicked() {
  
  out.loadPixels();
  
  println("Generating...");
  for (int i=0; i<out.pixels.length; i++) {
    out.pixels[i] = ((int)random(65536) << 16) + (int)random(65536);
  }
  counts = new int[4][256];
  
  int tmr = millis();
  println("Scanning...");
  // Prepare stats on data
  // Pass 1
  for (int i=0; i<out.pixels.length; i++) {
    counts[0][out.pixels[i] & 0xff]++;
    counts[1][((out.pixels[i] >> 8) & 0xff)]++;
    counts[2][((out.pixels[i] >> 16) & 0xff)]++;
    counts[3][((out.pixels[i] >> 24) & 0xff)]++;
  }

  println("Sorting...");
  // Sorts by each channel separately
  // Result is from smallest to largest (by numeric value)
  srtArray(out.pixels, datasrc, 0); //Blue
  srtArray(datasrc, out.pixels, 1); //Green
  srtArray(out.pixels, datasrc, 2); //Red
  srtArray(datasrc, out.pixels, 3); //Alpha
  
  out.updatePixels();
  
  println("Done. Integers sorted: " + out.pixels.length);
  println("Time including Scanning (ms): " + (millis() - tmr));
  
  redraw();
}


void srtArray(int[] tosort, int[] target, int depth) {
  
  int i=0;
  int x=0;
  int tx=0;
  
  if (tosort == target) {
    println("cannot copy to source");
    return;
  }
  
  int[] offs = new int[256];
  int[] subs = new int[256];
  
  tx = depth << 3;
  
  // Pass A
  // Calculates the offset of each level (0 - 255) within the array
  int addup = 0;
  int[] cur = counts[depth];//remove one level of indirection by taking a local reference
  for (i=1; i<256; i++) {
    addup += cur[i-1];
    offs[i] = addup;
  }
  
  // Pass B
  // location of datum is levelOffset + numOfSameLevelFound
  for (i=0; i<tosort.length; i++) {
    x = ((tosort[i] >> tx) & 0xff);
    
    target[offs[x] + subs[x]++] = tosort[i];
  }
  
}


void draw() {
  background(0,128,128);
  image(out,0,0,512,512);
}