package {
	
	import flash.display.Shape;
	import flash.errors.ScriptTimeoutError;
	import flash.events.Event;
	import flash.events.EventDispatcher;
	import flash.net.URLLoader;
	import flash.net.URLRequest;
	
	/**
	 * Sorts an array as an asynchronous operation using
	 * the Quicksort approach.
	 */
	public class Quicksort extends EventDispatcher {
		
		// ENTER_FRAME events dispatched by a composed DisplayObject
		// instance; one can be used for all Quicksort instances
		private static var enterFrameDispatcher:Shape = new Shape();
		
		// reference to the array to be sorted
		private var array:Array;
		
		// reference to the first recursive object
		private var rootOp:QuicksortOp;
		
		/**
		 * Constructor for new Quicksort instances.
		 * @param array The array to be sorted.
		 */
		public function Quicksort(array:Array) {
			this.array = array;
		}
		
		/**
		 * Starts the Quicksort operation.
		 */
		public function run():void {
			
			// initialize the root operation
			rootOp = new QuicksortOp(array, 0, array.length - 1);
			
			// set up ENTER_FRAME loop
			enterFrameDispatcher.addEventListener(Event.ENTER_FRAME, loopHandler, false, 0, true);
			// call the first iteration immediately
			loopHandler(null);
		}
		
		// ENTER_FRAME loop for asynchronous processing
		private function loopHandler(event:Event):void {
			
			try {
				
				// attempt to complete the call
				// if being delayed, an error will be thrown
				rootOp.call();
				
				// remove ENTER_FRAME event handler
				enterFrameDispatcher.removeEventListener(Event.ENTER_FRAME, loopHandler, false);
				// signal to listeners that processing is complete
				dispatchEvent(new Event(Event.COMPLETE));
				
			}catch(err:ScriptTimeoutError){
				// waiting for next frame
			}
		}
	}
}

import flash.errors.ScriptTimeoutError;

class QuicksortOp {
	
	private var array:Array; // array to sort
	private var start:int; // start index of array segment to sort
	private var end:int; // end index of array segment to sort
	private var pivot:int; // pivot index of array
	
	private var recursiveOp:QuicksortOp; // object used as recursive call
	private var processed:int;
	
	// indicates whether or not this
	// instance has thrown an error
	// durring processing; every instance
	// will throw once
	private var interrupted:Boolean = false;
	
	/**
	 * Constructor for new QuicksortOp instances.
	 */
	public function QuicksortOp(array:Array, start:int, end:int) {
		this.array = array;
		this.start = start;
		this.end = end;
		
		processed = 0;
	}
	
	/**
	 * Executes Quicksort logic and returns a result.
	 */
	public function call():void {
		
		// first block
		if (this.processed < 1) {
		
			// escape condition:
					
			if (!interrupted){
				interrupted = true;
				throw new ScriptTimeoutError("yield");
			}
			
			// validate data:
			
			if (array == null || end <= start || end >= array.length){
				// assume all sorting that can be 
				// done is done
				return;
			}
			
			// process:
	
			pivot = partition(array, start, end, int((end + start)/2));
			recursiveOp = new QuicksortOp(array, start, pivot - 1);
				
			processed = 1; // this block will no longer be run
		}
		
		// second block
		if (processed < 2) {
			
			// first recursion call; second block is all
			// logic after this throwable call leading up
			// to the next throwable call
			recursiveOp.call();
			
			// create new object for next, nested call
			recursiveOp = new QuicksortOp(array, pivot + 1, end);
			
			processed = 2; // this block will no longer be run
		}
		
		// second recursion call; final block
		// no condition is required for the final
		// block since no throwable call exists
		// after this logic
		recursiveOp.call();
		
		// cleaunup references
		recursiveOp = null;
		array = null;
		processed = 0;
	}

	/**
	 * Sorts an array segment.
	 */
	private function partition(array:Array, start:int, end:int, pivot:int):int {
		var value:* = array[pivot];
		swap(array, pivot, end);
		for (var i:int = start; i < end; i++) {
			if (array[i] <= value) {
				swap(array, start++, i);
			}
		}
		swap(array, end, start);
		return start;
	}
	
	/**
	 * Swaps two array values within indices a and b.
	 */
	private function swap(array:Array, a:int, b:int):void {
		var tmp:Number = array[a];
		array[a] = array[b];
		array[b] = tmp;
	}
}