Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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.
// 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();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment