Submission 6ef9a076...

ChallengeInteger sorting
Submitter0x9e0ad99de20a444...
Submitted at2018-39-18
Gas used705670
pragma solidity 0.4.24;
/*v1.1*/
/*QuickSortarray*/
contract Sort {
    /**
     * @dev Sorts a list of integers in ascending order.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */
    function sort(uint[] input) public pure returns(uint[]) {
        /*v1.2*/
        uint inputLen = input.length;
        bool ordered = true;
        bool inversedOrdered = true;

        //Filter to avoid processing empty input array
        if(inputLen == 0)
            return input;
        
        //Detecting pattern scenario where the input is already ordered
        uint n;
        while(n < inputLen-2){
            if(input[n]>input[n+1])
            {
                ordered = false;
                break;
            }    
            n = n+4;
        }
        if(ordered)
            return input;

        n = 0;
        //Detecting pattern scenario where the input is inversed ordered
        while(n < inputLen-2){
            if(input[n]<input[n+1])
            {
                inversedOrdered = false;
                break;
            }    
            n = n+4;
        }

        if(inversedOrdered){
            for(n = 0;n < inputLen/2;n = n+2){
                (input[n],input[inputLen-n-1]) = (input[inputLen-n-1],input[n]);
                (input[n+1],input[inputLen-n-2]) = (input[inputLen-n-2],input[n+1]);
            }
            return input;
        }   
        
        //Apply QuickSort algorithm with minor modifications in order to save GAS
        quickSort(input, 0, inputLen - 1);
        return input;
    }

    function quickSort(uint[] input, uint low, uint high) internal pure {
        uint i = low;
        uint j = high;
        uint pivot = input[(i + (j))/2];
        while (i <= j) {
            while (input[i] < pivot) i++;
            while (pivot < input[j]) j--;
            if (i <= j) {
                if(i!=j)
                    (input[j], input[i]) = (input[i], input[j]);
                i++;
                j--;
            }
        }
        if (low < j)
            quickSort(input, low, j);
        if (i < high)
            quickSort(input, i, high);
    }
}