Submission c08c136e...

ChallengeInteger sorting
Submitter0x53b21be84eece2e...
Submitted at2018-03-25
Gas used927448
/**
 * 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;

// 943484
contract Sort {
    function qsort(uint[] mem, uint start, uint end) public pure {
        uint len = end - start;
        uint a;
        uint b;
        uint c;
        uint d;
        uint tmp;
        
        if (len == 4) {
            a = mem[start];
            b = mem[start + 1];
            c = mem[start + 2];
            d = mem[start + 3];

            if (a > b) {tmp = b; b = a; a = tmp;}
            if (c > d) {tmp = d; d = c; c = tmp;}

            if (a > c) {tmp = c; c = a; a = tmp;}
            if (b > d) {tmp = d; d = b; b = tmp;}
            
            if (b > c) {tmp = c; c = b; b = tmp;}

            mem[start] = a;
            mem[start + 1] = b;
            mem[start + 2] = c;
            mem[start + 3] = d;
            return;            
        }

        if (len == 2) {
            a = mem[start];
            b = mem[start + 1];
            if (a > b) {
                mem[start] = b;
                mem[start + 1] = a;
            }
            return;
        }

        if (len < 2) return;

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

            if (i >= j) break;

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

        qsort(mem, start, i);
        qsort(mem, i, end);
    }

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

        return input;
    }
}