Submission 192ff3a0...

ChallengeInteger sorting
Submitterwicketh.eth
Submitted at2018-53-02
Gas used879035
contract Sort {
    
    // @author Remco Bloemen <[email protected]>
    
    function sort(uint[] input)
        public payable returns(uint[])
    {
        uint256 l = input.length;
        if (l < 2) return input;
        sort(input, 0, l - 1);
        return input;
    }

    function sort(uint[] memory input, uint256 lo, uint256 hi)
        internal view
    {
        uint256 d = hi - lo;
        if (d < 3) {
            // Optimize for two values
            if (d == 1) {
                uint256 a = input[lo];
                uint256 b = input[hi];
                if (b < a) {
                    input[lo] = b;
                    input[hi] = a;
                }
                return;
            }
            
            // Optimize for three values
            a = input[lo];
            b = input[lo + 1];
            uint256 c = input[hi];
            if (a < b) {
                if (b < c) {
                    return;
                } else {
                    if (c < a) {
                        input[lo] = c;
                        input[lo + 1] = a;
                        input[hi] = b;
                        return;
                    } else {
                        input[lo + 1] = c;
                        input[hi] = b;
                        return;
                    }
                }
            } else {
                if (a < c) {
                    input[lo] = b;
                    input[lo + 1] = a;
                    input[hi] = c;
                    return;
                } else {
                    if (b < c) {
                        input[lo] = b;
                        input[lo + 1] = c;
                        input[hi] = a;
                        return;
                    } else {
                        input[lo] = c;
                        input[lo + 1] = b;
                        input[hi] = a;
                        return;
                    }
                }
            }
        }
        
        // partition
        uint256 pivot = input[(lo + hi) / 2];
        uint256 i = lo;
        uint256 j = hi;
        while (true) {
            uint iv = input[i];
            uint jv = input[j];
            while (iv < pivot) {
                i++;
                iv = input[i];
            }
            while (jv > pivot) {
                j--;
                jv = input[j];
            }
            if (i >= j) {
                i = j + 1;
                break;
            }
            input[i] = jv;
            input[j] = iv;
            i += 1;
            j -= 1;
        }
                
        // Recurse
        if (lo < j) sort(input, lo, j);
        if (i < hi) sort(input, i, hi);
    }
}