Pushing counting sort down the stairs. Still neat to sort through 350M+ numbers in ~15 seconds on a below average contemporary PC, with no multi-threading or anything fancy.

OutOfMemoryError.pde

// PDE3

final int COUNT = int(pow(2,28)); // 350000000;
final int RANGE = COUNT;
      int[] rn = new int[COUNT];
      int[] sn = new int[COUNT];

void setup()
{ 
  println("generating " + rn.length + " numbers");

  for(int i = 0; i < rn.length; i++)
  {
    rn[i] = int( random(0f, RANGE) );
  }
   
  println("sorting");

  int t = millis();

  for(int i = 0; i < rn.length; sn[rn[i++]]++);
  
  //rn = sort(rn); // <- PDE3 sort() to measure against
      
  println("done in " + (millis()-t) + " milliseconds \n");
  /*
  for(int i = 0; i< COUNT; i++)
  {
    if (sn[i] > 0) print(i + "(" + sn[i] + ") "); 
  }
  */
  exit();
}