More On Radix and FlashSort

Let’s see how well our FlashSort and RadixSort functions are performing under specific conditions:

* when the keys in the array are uniques :
ex:[9 7 8 1 3 2 5 6 4 7 8]

* when the array is already sorted
ex:[ 1 2 3 4 5 6 7 8 9]

* when the array is sorted, but backward
ex:[9 8 7 6 5 4 3 2 1]

* when we have lots of duplicate keys
ex:[9 7 8 1 3 9 2 7 9 1 8 2 3 9 ] (ex 9 is there 4x times)

* when we have only 1 key (and nothing to sort)
[1 1 1 1 1 1 1 1 1 1 1 1]

Here my results (when sorting 200K integers):

Interesting to note:
* Radix time is very stable, no matter what is in the arrays. This is expected given the nature of the sorting algorithm.
* Flash sort time is pretty stable too, from 11ms to 18ms in my tests, excluding the special 1 key test, where we have an early exit.
* FlashSort beats Radix when all the elements to sort are identical, only 1 key.
* The worst case scenario for all those sorting algorithms is when there is no duplicate keys, except for Radix, where it doesn’t matter.
* Array native sort goes from 11 to 104 depending on what we have in the array, not very stable sorting time !

What do you get?

Test Code

here the code used for this post, you can find the radix and flashsort code in
those posts:radix flashSort.

		public static const sortTest_randomNoDuplicateKeys:int = 0;
		public static const sortTest_sorted:int = 1;
		public static const sortTest_invsorted:int = 2;
		public static const sortTest_duplicateKeys:int = 3;
		public static const sortTest_uniqeKey:int = 4;
		public static const sortTest_last:int = 5;
	
		private function sortIntegerTestAllBehaviors(n:int):void
		{
			for(var i:int=sortTest_randomNoDuplicateKeys;i<sortTest_last;i++)
				sortIntegerTest(n,i,false); //disable vectorSort, too slow
		}
		

		private function sortIntegerTestNum( nbr:int , sortBehavior:int = -1 , doVectorSort:Boolean=false):void
		{
			//generate nbr numbers:
			var i:int = -1;			
			var array:Vector.<int>  = new Vector.<int>(nbr);
			var array2:Vector.<int> = new Vector.<int>(nbr);
			var array3:Array 		= new Array(nbr);
			var array4:Vector.<int> = new Vector.<int>(nbr);
			var array5:Vector.<int> = new Vector.<int>(nbr);
			var array6:Vector.<int> = new Vector.<int>(nbr);
			var array7:Vector.<int> = new Vector.<int>(nbr);
			//var array8:Vector.<int> = new Vector.<int>(nbr);
			var sorted:Vector.<int> = new Vector.<int>(nbr);
			var half:int = nbr>>1;
			var duplicateKeys:Number = 1;
			//100 duplicates
			if(sortBehavior == sortTest_duplicateKeys)
				duplicateKeys = 0.01; //all keys 100 times
			if(sortBehavior == sortTest_uniqeKey)
				duplicateKeys = 0;//only 1 key for the entire array
			
			for(i=-1;(++i)<nbr;)
			{
				sorted[i] = (i-half) *duplicateKeys;
			}
			
			if(sortBehavior == sortTest_sorted)
			{	for(i=-1;(++i)<nbr;)
				{
					index = i; 
					/*array8[i] = */ array7[i] =  array6[i] =  array5[i] = array4[i] = array3[i] = array2[i] = array[i] = sorted[index];
				}
			}
			else if(sortBehavior == sortTest_invsorted)
			{	for(i=-1;(++i)<nbr;)
				{
					index = nbr-1-i; 
					/*array8[i] = */ array7[i] =  array6[i] =  array5[i] = array4[i] = array3[i] = array2[i] = array[i] = sorted[index];
				}
			}
			else
			{
				for(i=-1;(++i)<nbr;)
				{
					var index:int = Math.random()*sorted.length; 
					/*array8[i] = */ array7[i] =  array6[i] =  array5[i] = array4[i] = array3[i] = array2[i] = array[i] = sorted[index];
					sorted.splice(index,1);
				}
			}			
			sorted.length = nbr; //reset length - our temporary buffer for radix
			
			var time1:uint = getTimer();
			//RADIX
			{
				SortAlgorithms.RadixSort11(array,sorted);
			}
			var time2:uint = getTimer();			
			if(doVectorSort)
				array2.sort(sortFunc);
			var time3:uint = getTimer();
			//Array
			{	
				//some code commented to time the copy back and forth from Vector to Array to Vector
				var ary:Array = array3;
				//var ary:Array = new Array(array3.length);
				//for(var yy:int =-1,max:int=array3.length;(++yy-max)>>>31;)
				//	ary[yy]=array3[yy];
				ary.sort( Array.NUMERIC);
				//array3 = Vector.<int>(ary);
			}
			var time4:uint = getTimer();
			//Shell sort
			{
				SortAlgorithms.shellSort(array4);
			}
			var time5:uint = getTimer();
			//QuickSort
			{
				SortAlgorithms.NonRecursiveQuickSortInt(array5);
			}
			var time6:uint = getTimer();
			//Flashsort
			{
				SortAlgorithms.flashSortInt3(array6);
			}
			var time7:uint = getTimer();
			//Radix Alchemy
			{
				SortAlgorithms.RadixSorAlchemyt11(array7);
			}
			var time8:uint = getTimer();
			//verify sorting in our sorted array
			/*
			verifySort(sorted);
			verifySort(array2);
			verifySort(array3);
			verifySort(array4);
			verifySort(array5);
			verifySort(array6);
			verifySort(array7);
			*/
			
			var str:String = "sortInt_k="+nbr;
				switch(sortBehavior)
				{
					case sortTest_randomNoDuplicateKeys:str+="_uniqueKeys";break;
					case sortTest_sorted:str+="_preSorted";break;
					case sortTest_invsorted:str+="_preInvSorted";break;
					case sortTest_duplicateKeys:str+="_dupKeys";break;
					case sortTest_uniqeKey:str+="_1key";break;
				}
				
				if(doVectorSort)
					setTest(str, "Vector.sort:"  , 	 	time3-time2 );
				setTest( str , "Shell.sort"   ,   		time5-time4 );
				setTest( str , "Array.sort"   ,   		time4-time3 );
				setTest( str ,"Quick.sort"   ,   		time6-time5 );
				setTest( str ,"Flash.sort"   ,   		time7-time6 );
				setTest( str ,"Radix.sort"   ,   		time2-time1 );
				setTest( str , "RadixAlchemy.sort"   ,  time8-time7 );
		}