(function( $ ) {

    var zero = '0'.charCodeAt(0);
    var nine = '9'.charCodeAt(0);

    var lastops = 0;
    var lastcycles = 0;
    var timer;

    function isNumber(value)
    {
        var isnum = true;
        
        if(typeof value == "string")
        {
            for(var i=0; i<value.length && isnum; i++)
            {
                isnum = (value.charCodeAt(i) >= zero && value.charCodeAt(i) <= nine);
            }
        }
        else
        {
            isnum = (typeof value == "number");
        }

        return isnum;
    }

    function compare(value1, value2, info1, info2)
    {
        if(!info1) info1 = {
            isnull: (!value1 && value1 !== 0 && !(typeof value == "string")),
            isnum: isNumber(value1)
        };

        var isnull1 = info1.isnull;
        var isnull2 = info2.isnull;
        var isnum1 = info1.isnum;
        var isnum2 = info2.isnum;

        if(isnull1 && isnull2) return 0;
        if(isnull1 && !isnull2) return 1;
        if(!isnull1 && isnull2) return -1;

        if(isnum1 && !isnum2) return -1;
        if(!isnum1 && isnum2) return 1;
        if(isnum1 && isnum2) return Number(value1) - Number(value2);
        
        if(value1 < value2) return -1;
        if(value1 > value2) return 1;

        return 0;
    }

    function stringCompare(value1, value2, info1, info2)
    {
        if(!info1) info1 = {
            isnull: (!value1 && value1 !== 0 && !(typeof value == "string"))
        };

        var isnull1 = info1.isnull;
        var isnull2 = info2.isnull;

        if(isnull1 && isnull2) return 0;
        if(isnull1 && !isnull2) return 1;
        if(!isnull1 && isnull2) return -1;

        if(value1 < value2) return -1;
        if(value1 > value2) return 1;

        return 0;
    }

    function getCompareFunction(value)
    {
        if(!value) return compare;
        if(value instanceof Function) return value;
        if(value.toLowerCase() == "string") return stringCompare;

        return compare;
    }

    function invert(compare)
    {
        return function(value1, value2, info1, info2) {
            return -compare(value1, value2, info1, info2);
        }
    }

    $.sort = function(data, options)
    {
        var results = new Array();
        var list = null;
        var tail = null;
        var lastLink = null;
        var index = 0;

        var cycle = (options && options.cycle) || 100;
        var indexSize = (options && options.indexSize) || 10;
        var indexChars = (options && options.indexChars) || 2;
        var compare = getCompareFunction(options && options.compare);
        var customCompare = !!(options && options.compare && options.compare != "default");
        var caseSensitive = !!(options && options.caseSensitive);
        var notification = (options && options.notification) || null;
        var notify = (options && options.notify) || (notification ? 1500 : 0);
        var lastNotification = new Date().getTime();
        var order = ((options && options.order) || 'asc') != 'desc';

        var numindex = new Array(Math.floor(data.length/indexSize)+1);
        var treeindex = {};
        var ops = 0;
        var cycles = 0;

        if(data == "ops") return lastops;
        if(data == "cycles") return lastcycles;
        if(!data) $.error("No data passed to sort(). Example: var results = sort([2,1,3]);")
        if(!(data instanceof Array)) $.error("Object to be sorted is not an array.");
        if(!order) compare = invert(compare);
        if(timer) clearTimeout(timer);

        function indexString(value, link)
        {
            var number = 0;
            var mask = 0x01 << (indexChars * 8 - 1);
            var start = treeindex;
            var index;

            for(var i=0; i<indexChars; i++)
            {
                number <<= 8;
                number += (i < value.length) ? value.charCodeAt(i) : 0;
            }

            while(mask > 0x01)
            {
                index = (number & mask) ? 1 : 0;

                if(!start[index]) start[index] = {0:false, 1:false};

                start = start[index];
                mask >>= 1;
            }

            index = Math.floor(index / 10);

            index = (number & mask) ? 1 : 0;

            if(!start[index]) start[index] = {head:false, tail:false};
            if(!start[index].head || compare(value, start[index].head.value, link.info, start[index].head.info) < 0) start[index].head = link;
            if(!start[index].tail || compare(value, start[index].tail.value, link.info, start[index].tail.info) >= 0) start[index].tail = link;
        }

        function lookupString(value)
        {
            var number = 0;
            var mask = 0x01 << (indexChars * 8 - 1);
            var start = treeindex;
            var index;

            var score1;
            var score2;

            for(var i=0; i<indexChars; i++)
            {
                number <<= 8;
                number += (i < value.length) ? value.charCodeAt(i) : 0;
            }

            while(mask > 0x01)
            {
                index = (number & mask) ? 1 : 0;

                if(!start[index])
                {
                    number = index ? 0x7FFFFFFF : 0x00;
                    index = index ? 0 : 1;
                }

                if(!start[index]) return null;

                start = start[index];
                mask >>= 1;
            }

            index = Math.floor(index / 10);
            index = (number & mask) ? 1 : 0;

            if(!start[index]) index = index ? 0 : 1;

            if(!start[index]) return null;
            if(start[index].head == start[index].tail) return start[index].tail;

            score1 = score(value, start[index].head.value);
            score2 = score(value, start[index].tail.value);

            if(score1 > score2) return start[index].head;
            else return start[index].tail;
        }

        function score(value1, value2)
        {
            var length = Math.min(value1.length, value2.length);

            for(var i=0; i<length; i++)
            {
                if(value1.charCodeAt(i) != value2.charCodeAt()) return i;
            }

            return length;
        }

        function insert(object, value, start)
        {
            var result;
            var info = {
                isnull: (!value && value !== 0 && !(typeof value == "string")),
                isnum: (!customCompare && isNumber(value))
            };
            
            if(customCompare) delete info.isnum;

            if(!list)
            {
                list = {
                    value: value,
                    object: object,
                    info: info
                };

                tail = list;

                return;
            }

            while((result = compare(value, start.value, info, start.info)) > 0 && start.next)
            {
                ops++;
                start = start.next;
            }

            if(result < 1)
            {
                var link = {
                    next: start,
                    last: start.last,
                    value: value,
                    object: object,
                    info: info
                };

                start.last = link;
                registerIndex(value, link);
                
                if(link.last) link.last.next = link;
                if(start === list) list = link;
            }
            else
            {
                start.next = {
                    last: start,
                    value: value,
                    object: object,
                    info: info
                };

                tail = start.next;
                registerIndex(value, tail);
            }
        }

        function insertReverse(object, value, start)
        {
            var result;
            var info = {
                isnull: (!value && value !== 0 && !(typeof value == "string")),
                isnum: (!customCompare && isNumber(value))
            };

            if(customCompare) delete info.isnum;

            if(!list)
            {
                list = {
                    value: value,
                    object: object,
                    info: info
                };

                tail = list;

                return;
            }
            
            while((result = compare(value, start.value, info, start.info)) < 0 && start.last)
            {
                ops++;
                start = start.last;
            }

            if(result >= 0)
            {
                var link = {
                    next: start.next,
                    last: start,
                    value: value,
                    object: object,
                    info: info
                };

                start.next = link;
                registerIndex(value, link);

                if(link.next) link.next.last = link;
                if(start === tail) tail = link;
            }
            else
            {
                start.last = {
                    next: start,
                    value: value,
                    object: object,
                    info: info
                };

                list = start.last;
                registerIndex(value, list);
            }
        }

        function registerIndex(value, link)
        {
            var index = 0;
            var current;

            if(link.info.isnum)
            {
                numindex[Math.floor(Number(value)/indexSize)] = link;
            }
            else if(value && typeof value == "string" && value.length > 0)
            {
                indexString(value, link);
            }

            lastLink = link;
        }

        function getStartPosition(value)
        {
            var index;
            var fall;

            if(!value && typeof value == "string") return list;
            if(!value && value !== 0) return tail;
            if(!value) return list;

            if(!customCompare && isNumber(value))
            {
                fall = index = Math.floor(Number(value)/indexSize);

                while(!numindex[index] && index >= 0 && fall-index > 1000) index--;
                
                return (numindex[index] || lastLink || list);
            }

            if(typeof value == "string")
            {
                if(value.length < 1) return list;

                return (lookupString(value) || lastLink || list);
            }

            return (lastLink || list);
        }

        function performSort()
        {
            var time = new Date().getTime();
            var currentTime;
            var value;
            var start;

            cycles++;

            while(index < data.length && (currentTime = new Date().getTime()) < (time + cycle))
            {
                if(options && options.property) value = data[index][options.property];
                else value = data[index];

                if(!caseSensitive && typeof value == "string") value = value.toLowerCase();

                start = getStartPosition(value);

                if(!start || compare(value, start.value, null, start.info) >= 0)
                {
                    insert(data[index], value, start);
                }
                else
                {
                    insertReverse(data[index], value, start);
                }

                index++;
            }

            lastops = ops;
            lastcycles = cycles;

            if(notify && currentTime > (lastNotification + notify) && index < data.length)
            {
                start = list; // Go back to the beginning

                for(var i=0; i<index && start; i++)
                {
                    results[i] = start.object;
                    start = start.next;
                }

                notification(index, results);

                lastNotification += notify;
            }

            if(index < data.length)
            {
                timer = setTimeout(performSort, cycle);
            }
            else if(options && options.finished)
            {
                start = list; // Go back to the beginning

                for(var i=0; i<index && start; i++)
                {
                    results[i] = start.object;
                    start = start.next;
                }

                // Sanity check
                if(results.length != index) $.error("Found " + results.length + " items, expected " + index);

                timer = null;
                options.finished(results);
            }
        }

        timer = setTimeout(performSort, cycle);

        return results;
    }
})(jQuery);