package com.meduzik.utils
{
    public class VectorSort{
        public static function Sort(v:*, comparator:Function):void
        {
            var n:int = v.length;
            if ( n >= 30 ) {
                QSort(v, comparator, 0, n);
            }else {
                InsertionSort(v, comparator, 0, n);
            }
        }

        private static function QSort(v:*, comparator:Function, begin:int, end:int):void
        {
        tailcall:
            var x1:* = v[begin];
            var x2:* = v[(begin + end) >> 1];
            var x3:* = v[end - 1];

            var c1:Boolean = comparator(x1, x2) < 0;
            var c3:Boolean = comparator(x2, x3) < 0;

            var pivot:*;

            if ( c1 == c3 ) {
                pivot = x2;
            }else{
                var c2:Boolean = comparator(x1, x3) < 0;
                if ( c2 != c3 ) {
                    pivot = x3;
                }else {
                    pivot = x1;
                }
            }

            var low:int = begin;
            var mid:int = begin;
            var high:int = end;
            for ( var i:int = begin; i < high; i++ ) {
                var cmp:Number = comparator(v[i], pivot);
                if ( cmp < 0 ) {
                    var tmp:* = v[low];
                    v[low] = v[i];
                    v[i] = tmp;

                    low++;
                }else if ( cmp > 0 ) {
                    --high;
                    tmp = v[high];
                    v[high] = v[i];
                    v[i] = tmp;
                    i--;
                }
            }

            var first:int = low - begin;
            var second:int = end - high;

            if ( first <= 8 ) {
                InsertionSort(v, comparator, begin, low);
                if ( second <= 8 ){
                    InsertionSort(v, comparator, high, end);
                }else {
                    begin = high;
                    goto tailcall;
                }
            }else if ( second <= 8 ) {
                InsertionSort(v, comparator, high, end);
                end = low;
                goto tailcall;
            }else {
                if ( first < second ) {
                    QSort(v, comparator, begin, low);
                    begin = high;
                }else {
                    QSort(v, comparator, high, end);
                    end = low;
                }
                goto tailcall;
            }
        }

        [Inline]
        private static function InsertionSort(v:*, comparator:Function, begin:int, end:int):void
        {
            var n:int = end - begin;
            for ( var i:int = 0; i < n; i++ ) {
                var j:int = i + begin;
                var x:* = v[j];
                while ( j > begin && comparator(x, v[j - 1]) < 0 ) {
                    v[j] = v[j - 1];
                    j--;
                }
                v[j] = x;
            }
        }
    }
}