Super fast SortOn with FlashSort !

In this post Super fast sorting with FlashSort !, I presented a really fast algoryhm to sort integers.

What about changing it to try to beat the Array.sortOn, and by this making it more usable ?

So as far as the API, we want to go from

static public function 
flashSortInt2(a:Vector.<int> , multiplier:Number = 0.43):void
{
}

to something like that:

static public function 
flashSortOn(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
{
}

Attempt1

So what we can do, is to simply change each access to a[index] in the code to
o[index][key]

Here with the changes:

		static public function flashSortOn2(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
		{
			var n:int = o.length;
			var i:int = 0, j:int = 0, k:int = 0;
			var m:int = n*multiplier;if(m>262143)m=262143;
			var l:Vector.<int> = new Vector.<int>(m);
			var anmin:int = o[0][key];
			var anmax:int = anmin;
			var nmax:int  = 0;
			var nmove:int = 0;
			var lk:int;
			i =0;
			
			var kmin:int,kmax:int,kimin:int,kimax:int;
			for (i=0; (i+=2) < n;)
			{
				if( (kmin = o[i][key])>(kmax = o[i-1][key]))
				{
					if (kmax< anmin) anmin = kmax;
					if (kmin> anmax) { anmax = kmin; nmax = i;}										
				}
				else
				{
					if (kmin< anmin) anmin = kmin;
					if (kmax > anmax) { anmax = kmax; nmax = i-1;}					
				}				
			}			
			if(--i < n)
			{
				if ((k = o[i][key]) < anmin) anmin = k;
				else if (k > anmax) { anmax = k; nmax = i;}
			}
						
			if (anmin == anmax) return;
			
			var c1:int = ((m - 1)<<13) / (anmax - anmin);
			
			for (i = -1; ++i < n;)
			{
				++l[(c1*(o[i][key] - anmin))>>13];
			}
			
			lk = l[0];
			for (k = 0; ++k < m;)
			{
				lk = (l[k] += lk);
			}
			
			var holdo:Object = o[nmax];			
			o[nmax] = o[0];
			o[0] = holdo;
			
			var flasho:Object;
			j = 0;
			k = (m - 1);
			i = (n - 1);
			
			while (nmove < i)
			{
				while (j >= l[k])
				{
					k = (c1 * (o[ (++j)][key] - anmin))>>13;
				}
				
				flasho = o[j];
				var flash:int  = flasho[key];
				
				lk = l[k];
				while (j !=lk)
				{
					holdo = o[(lk = (--l[(k = ((c1 * (flash - anmin))>>13))]))];
					o[lk] = flasho;
					flasho = holdo;
					++nmove;									
				}
				
			}
			
			for(j = 0; ++j < n;)
			{
				holdo = o[j];
				var hold:int = holdo[key];
				i = j;
				while((--i >= 0) && (((holdo=o[i])[key]) > hold))
				{	
					o[i+1] = holdo;
				}
				o[(i+1)] = holdo;				
			}	
		}

Great, with minimum changes, we have a flashSort with a key sortOn capability
… lets try, humm … slower than Array.sort, much slower.

Attemp2

So, what is slow here, is to access the o[index][key] over and over again,
One thing we can do, is to copy all the keys into a separate Vector.<int> (assuming the key is an integer),in the first loop when we first find the min and the max, and from there use our temporary buffer..
Then, later, each time we swap or move something in that Vector from one index to another, we can apply the same transform in our o object Vector.
Here the code:

		static public function flashSortOn(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
		{
			var n:int = o.length;
			var i:int = 0, j:int = 0, k:int = 0;
			var a:Vector.<int> = new Vector.<int>(n);
			var m:int = n*multiplier;if(m>262143)m=262143;
			var l:Vector.<int> = new Vector.<int>(m);
			var anmin:int = a[0] = o[0][key];
			var anmax:int = anmin;
			var nmax:int  = 0;
			var nmove:int = 0;
			var lk:int;
			i =0;
			
			var kmin:int,kmax:int,kimin:int,kimax:int;
			for (i=0; (i+=2) < n;)
			{
				a[i] = kmin = o[i][key];
				a[i-1] = kmax = o[i-1][key];
				
				if( kmin>kmax)
				{
					if (kmax< anmin) anmin = kmax;
					if (kmin> anmax) { anmax = kmin; nmax = i;}										
				}
				else
				{
					if (kmin< anmin) anmin = kmin;
					if (kmax > anmax) { anmax = kmax; nmax = i-1;}					
				}				
			}			
			if(--i < n)
			{
				a[i] = k = o[i][key];
				
				if (k < anmin) anmin = k;
				else if (k > anmax) { anmax = k; nmax = i;}
			}
						
			//var time3:int = getTimer();
			//time2 = time3-time2;
			//trace(time1,time2);
			
			if (anmin == anmax) return;
			
			var c1:int = ((m - 1)<<13) / (anmax - anmin);
			
			for (i = -1; ++i < n;)
			{
				++l[(c1*(a[i] - anmin))>>13];
			}
			
			lk = l[0];
			for (k = 0; ++k < m;)
			{
				lk = (l[k] += lk);
			}
			
			//swap a[nmax] and a[0]
			var hold:int = anmax;
			var holdo:Object = o[nmax];
			
			a[nmax] = a[0];
			o[nmax] = o[0];
			a[0] = hold;
			o[0] = holdo;
						
			var flash:int;
			var flasho:Object;
			j = 0;
			k = (m - 1);
			i = (n - 1);
			
			while (nmove < i)
			{
				while (j >= l[k])
				{
					k = (c1 * (a[ (++j)] - anmin))>>13;
				}
				
				flash = a[j];
				flasho = o[j];
				
				lk = l[k];
				while (j !=lk)
				{
					hold = a[(lk = (--l[(k = ((c1 * (flash - anmin))>>13))]))];
					holdo = o[lk];
					a[lk] = flash;
					o[lk] = flasho;
					flash = hold;
					flasho = holdo;
					++nmove;									
				}
				
			}
			
			for(j = 0; ++j < n;)
			{
				hold = a[j];
				holdo = o[i=j];
				while((--i >= 0) && ((k=a[i]) > hold))
				{	
					o[i+1] = o[i];
					a[i+1] = k;
				}
				if(++i != j)
				{
					a[i] = hold;
					o[i] = holdo;
				}
			}	
		}

Attempt3

Final attempt, we can rewritte this with Alchemy, alchemy byteArray is used as our temporary buffer…

static public function flashSortOnAlchemy(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
		{
			var n:int = o.length;
			var i:int = 0, j:int = 0, k:int = 0;
			var m:int = n*multiplier;if(m>262143)m=262143;
			var m4:int = m<<2;
			var m4end:int = m4 + (n<<2);
			var anmin:int = o[0][key];
			var anmax:int = anmin;
			var nmax:int  = 0;
			var nmove:int = 0;
			var lk:int;
			i =0;
			var zero:Number =0;
			for(i=-8;(i+=8)<m4;)
			{
				fastmem.fastSetDouble(zero,i);				
			}
			
			//set first element
			fastmem.fastSetI32(anmin,m4);
			
			
			//method 1 - 1 index / iteration
			/*
			var time1:int = getTimer();
			for (; ++i < n;)
			{
			if ((k = a[i]) < anmin) anmin = k;
			else if (k > anmax) { anmax = k; nmax = i;}
			}
			
			var time2:int = getTimer();
			
			time1 = time2-time1;
			trace(anmin,anmax,nmax);
			time2 = getTimer();
			//anmax = anmin = a[0]; - enable that if you want to test both mryhois
			*/
			//method2 - do 2 indexes / iterations
			var kmin:int,kmax:int,kimin:int,kimax:int;
			var a_i:int = m4+4; //start at element 1
			for (i=0; (i+=2) < n;)
			{
				//a[i-1] = kmax = o[i-1][key];
				fastmem.fastSetI32(kmax = o[i-1][key],a_i);

				//a[i] = kmin = o[i][key];
				fastmem.fastSetI32(kmin = o[i][key],a_i+4);
					
				a_i+=8;
				
				if( kmin>kmax)
				{
					if (kmax< anmin) anmin = kmax;
					if (kmin> anmax) { anmax = kmin; nmax = i;}										
				}
				else
				{
					if (kmin< anmin) anmin = kmin;
					if (kmax > anmax) { anmax = kmax; nmax = i-1;}					
				}				
			}			
			if(--i < n)
			{
				//a[i] = k = o[i][key];
				fastmem.fastSetI32(k = o[i][key],a_i);
				
				if (k < anmin) anmin = k;
				else if (k > anmax) { anmax = k; nmax = i;}
			}
			
			
			if (anmin == anmax) return;
			
			var c1:int = ((m - 1)<<13) / (anmax - anmin);
			var tilde3:int = ~3;
			;
			for (a_i = m4-4; (a_i+=4) < m4end;)
			{				
				fastmem.fastSetI32(fastmem.fastGetI32((k=(((c1*(fastmem.fastGetI32(a_i) - anmin))>>11) & tilde3)))+1,k);
			}
			
			lk = fastmem.fastGetI32(0);
			for (k = 0; (k+=4) < m4;)
			{
				fastmem.fastSetI32((lk += fastmem.fastGetI32(k)),k);
			}

						
			//swap a[nmax] and a[0]
			var hold:int = anmax;
			var holdo:Object = o[nmax];
			
			//a[nmax] = a[0];
			fastmem.fastSetI32(fastmem.fastGetI32(m4),m4+(nmax<<2));
			o[nmax] = o[0];
			//a[0] = hold;
			fastmem.fastSetI32(hold,m4);
			o[0] = holdo;
			
			var flash:int;
			var flasho:Object;
			j = 0;
			k = (m - 1);
			i = (n - 1);
			
			while (nmove < i)
			{
				a_i = m4 + (j<<2);
				while (j >= fastmem.fastGetI32(k))
				{
					k = ((c1 * (fastmem.fastGetI32(a_i+=4) - anmin))>>11)&tilde3;
					j++;
				}
				
				flash = fastmem.fastGetI32(m4 +(j<<2));
				flasho = o[j];
				
				lk = fastmem.fastGetI32(k);				
				while (j !=lk)
				{
					hold =  fastmem.fastGetI32(m4 + ((lk = (fastmem.fastGetI32((k = (((c1 * (flash - anmin))>>11)&tilde3)))-1))<<2));
					fastmem.fastSetI32(lk,k);
					
					//hold = a[(lk = (--l[(k = ((c1 * (flash - anmin))>>13))]))];
					holdo = o[lk];
					//a[lk] = flash;
					fastmem.fastSetI32(flash,m4+(lk<<2));
					o[lk] = flasho;
					flash = hold;
					flasho = holdo;
					++nmove;									
				}
				
			}
			
			for(j = 0; ++j < n;)
			{
				//hold = a[j];
				hold = fastmem.fastGetI32(m4 + (j<<2));
				holdo = o[i=j];
				while((--i >= 0) && ((k=fastmem.fastGetI32(m4 + (i<<2))) > hold))
				{	
					o[i+1] = o[i];
					//a[i+1] = k;
					fastmem.fastSetI32(k,m4 + ((i+1)<<2)); 
					
				}
				if(++i != j)
				{
					//a[i] = hold;
					fastmem.fastSetI32(hold,m4 + (i<<2));
					o[i] = holdo;
				}
			}	
		}		

Okay, lets try !!!!

* we are faster than the Array.sortOn !
* alchemy changes didn’t help

What do you get?