Submission 40293046...

ChallengeInteger sorting
Submitter0x9e0ad99de20a444...
Submitted at2018-42-14
Gas used929854
pragma solidity 0.4.24;
/*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[]) {
        uint inputLen = input.length;
        bool ordered = true;
        bool inversedOrdered = true;

        if(inputLen == 0)
            return input;

        for(uint n = 0;n < inputLen-2;n++){
            if(input[n] > input[n+1]){
                ordered = false;
                break;
            }
        }
        if(ordered)
            return input;

        for(n = 0;n < inputLen-2;n++){
            if(input[n] < input[n+1]){
                inversedOrdered = false;
                break;
            }
        }

        if(inversedOrdered){

            for(n = 0;n < inputLen/2;n++){
                (input[n],input[inputLen-n-1]) = (input[inputLen-n-1],input[n]);
            }
            return input;
        }   


        sortLoop(input, 0, int(inputLen - 1));
        return input;
    }

    function sortLoop(uint[] input, int lo, int hi) internal pure {
        if(lo < hi) {
            int p = partition(input, lo, hi);
            sortLoop(input, lo, p - 1);
            sortLoop(input, p + 1, hi);
        }
    }

    function partition(uint[] input, int lo, int hi) internal pure returns(int) {
        uint pivot = input[uint(hi)];
        int i = lo - 1;
        for(int j = lo; j < hi; j++) {
            if(input[uint(j)] < pivot) {
                i += 1;
                (input[uint(i)], input[uint(j)]) = (input[uint(j)], input[uint(i)]);              
            }
        }
        (input[uint(i + 1)], input[uint(hi)]) = (input[uint(hi)], input[uint(i + 1)]);
        return i + 1;
    }
}