Submission b929dac0...

ChallengeInteger sorting
Submitterwicketh.eth
Submitted at2018-47-31
Gas used999377
contract Sort {
    function sort(uint[] input) public pure returns(uint[]) {
        sort(input, 0, int(input.length - 1));
        return input;
    }

    function sort(uint[] input, int lo, int hi)
        internal pure
    {
        if(lo < hi) {
            if (hi - lo == 1) {
                uint lov = input[uint(lo)];
                uint hiv = input[uint(hi)];
                if (lov > hiv) {
                    input[uint(lo)] = hiv;
                    input[uint(hi)] = lov;
                }
            } else {
                int slo;
                int shi;
                (slo, shi) = partition(input, lo, hi);
                sort(input, lo, slo);
                sort(input, shi, hi);
            }
        }
    }

    function partition(uint[] input, int lo, int hi)
        internal pure
        returns(int, int)
    {
        uint pivot = input[uint((lo + hi) / 2)];
        int i = lo;
        int j = hi;
        while (true) {
            uint iv = input[uint(i)];
            uint jv = input[uint(j)];
            while (iv < pivot) {
                i++;
                iv = input[uint(i)];
            }
            while (jv > pivot) {
                j--;
                jv = input[uint(j)];
            }
            if (i >= j) {
                return (j, j + 1);
            }
            input[uint(i)] = jv;
            input[uint(j)] = iv;
            i += 1;
            j -= 1;
        }
    }
}