/*
    MooTools quicksort implementation.
    Copyright Michael Sörensen / Apto Networks / www.apto.dk
    Version 1.0 - 24th of August 2009.
     
    Textbook implementation of the quicksort algorithm.
     
    Usage:
    var quicksort = new QuickSort();
    var arrayToBeSorted = quicksort.sort(arrayToBeSorted, 'ASC');
     
    For reverse sorting use:
    var quicksort = new QuickSort();
    var arrayToBeSorted = quicksort.sort(arrayToBeSorted, 'DESC');
     
    To sort an array of Objects use:
    var quicksort = new QuickSort({key: 'content');
    var arrayToBeSorted = quicksort.sort(arrayToBeSorted, 'ASC');
    -- where content is the attribute, in the array to sort on.
    I.e. [{id: 3, content: 'some text aaa'},{id: 2, content: 'some text ccc'},{id: 5, content: 'some text bbb'}]
     
     
    */
     
     
    var QuickSort = new Class({    
            Implements: [Options],
            options: {
                    key: false
            },
            initialize: function(options) {
                    //set options
                    this.setOptions(options);              
            },
            sort: function(arr, direction){
                    var a = this.qsort(arr);
                    if(direction=='DESC') {
                            a.reverse();
                    }
                    return a;
            },
            qsort: function(arr) {
                    var key = this.options.key;
                    var cl = this;
                    var less = new Array();
                    var more = new Array();
                   
                   
                    //if the passed array is zero length or just one, return
                    if(arr.length<=1) {
                            return arr;    
                    }
                   
                    // if array to be sorted is only 2, skip recursion and sort and return
                    if(arr.length==2) {
                            if(!key) {
                                    if(arr[0]<arr[1]) {
                                            return arr;    
                                    }
                                    else {
                                            arr.reverse();
                                            return arr;    
                                    }
                            }
                            else {
                                    if(arr[0][key]<arr[1][key]) {
                                            return arr;    
                                    }
                                    else {
                                            arr.reverse();
                                            return arr;    
                                    }      
                            }
                    }
                   
                    //if length is longer than 2, do the normal recursion
                    var pivot = arr.splice(Math.ceil(arr.length/2), 1)[0];
                   
                    //run through items and compare with pivot
                    arr.each(function(item, index){
                            //check if it's object sort or normal sort
                            if(!key) {
                                    if(item<=pivot) {
                                            less.push(item);       
                                    }
                                    else {
                                            more.push(item);       
                                    }                              
                            }
                            //Using key for object comparison
                            else {
                                    if(item[key]<=pivot[key]) {
                                            less.push(item);       
                                    }
                                    else {
                                            more.push(item);
                                    }
                            }
                             
                    });
                   
                    // recursively sort the rough subarrays
                    less = cl.qsort(less);
                    more = cl.qsort(more);
     
                    //concatenate the sorted arrays and return
                    return less.concat([pivot]).concat(more);
                   
            }
    });