Submission c694f702...

ChallengeInteger sorting
Submitter0x53b21be84eece2e...
Submitted at2018-08-27
Gas used911459
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */
pragma solidity ^0.4.24;

// 931751
contract Sort {
    // event Qsort(uint, uint, uint);
    function qsort(uint[] mem, uint start, uint end) public pure {
        uint tmp = end - start;
        // emit Qsort(tmp, start, end);
        uint a;
        uint b;
        uint i;
        uint j;
        
        if (tmp == 4) {
            a = mem[start];
            b = mem[start + 1];
            i = mem[start + 2];
            j = mem[start + 3];

            if (a > b) {tmp = b; b = a; a = tmp;}
            if (i > j) {tmp = j; j = i; i = tmp;}

            if (a > i) {tmp = i; i = a; a = tmp;}
            if (b > j) {tmp = j; j = b; b = tmp;}
            
            if (b > i) {tmp = i; i = b; b = tmp;}

            mem[start] = a;
            mem[start + 1] = b;
            mem[start + 2] = i;
            mem[start + 3] = j;
        } else if (tmp > 2) {
            tmp = mem[(start + end) / 2];
            i = start;
            j = end - 1;
            while(true) {
                a = mem[i];
                b = mem[j];
                while (a < tmp) {
                    a = mem[++i];
                }
                while (b > tmp) {
                    b = mem[--j];
                }

                if (i >= j) break;

                mem[i++] = b;
                mem[j--] = a;
            }

            qsort(mem, start, i);
            qsort(mem, i, end);
        } else if (tmp == 2) {
            a = mem[start];
            b = mem[start + 1];
            if (a > b) {
                mem[start] = b;
                mem[start + 1] = a;
            }
        }
    }

    function sort(uint[] input) public pure returns(uint[]) {
        qsort(input, 0, input.length);

        return input;
    }
}