Submission 0541e7d0...

ChallengeInteger sorting
Submitter0xabcdef0db461f2f...
Submitted at2018-18-03
Gas used1087641
/**
 * 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;

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[]) {
        if (input.length < 2) {
            return input;
        }
        if (input.length == 2) {
            if (input[0] > input[1]) {
                (input[0], input[1]) = (input[1], input[0]);
            }
            return input;
        }
        dualQuickSortAsc(input, 0, input.length-1);
        return input;
    }

    function choosePivot(uint[] input, uint head, uint tail) internal pure returns(uint, uint) {
        uint diff = (tail - head) / 3;
        uint left = head + diff;
        uint right = tail - diff;
        if (input[head] > input[tail]) {
            (input[head], input[tail]) = (input[tail], input[head]);
        }
        if (input[head] > input[right]) {
            (input[head], input[right]) = (input[right], input[head]);
        }
        if (input[head] > input[left]) {
            (input[head], input[left]) = (input[left], input[head]);
        }
        if (input[left] > input[right]) {
            (input[left], input[right]) = (input[right], input[left]);
        }
        if (input[left] > input[tail]) {
            (input[left], input[tail]) = (input[tail], input[left]);
        }
        if (input[right] > input[tail]) {
            (input[right], input[tail]) = (input[tail], input[right]);
        }
        return (input[left], input[right]);
    }

    function insertSortAsc(uint[] memory input, uint head, uint tail) internal pure {
        for (uint i = head+1; i <= tail; i++) {
            uint tmp = input[i];
            uint j;
            for (j = i-1; j >= head; j--) {
                if (tmp > input[j]) {
                    break;
                } else {
                    input[j+1] = input[j];
                }
            }
            input[j+1] = tmp;
        }
    }

    function dualQuickSortAsc(uint[] memory input, uint head, uint tail) internal pure
    {
        if (tail - head <= 16 && head != 0) {
            insertSortAsc(input, head, tail);
            return;
        }
        uint x;
        uint y;
        (x, y) = choosePivot(input, head, tail);
        uint h = head+1;
        uint t = tail-1;
        while (input[h] < x) {
            h++;
        }
        while (input[t] > y) {
            t--;
        }
        for (uint k = h; k <= t; ) {
            if (input[k] < x) {
                (input[h], input[k]) = (input[k], input[h]);
                h++;
                k++;
            } else if (input[k] > y) {
                (input[t], input[k]) = (input[k], input[t]);
                t--;
            } else {
                k++;
            }
        }
        if (h < t) {
            dualQuickSortAsc(input, h, t);
        }
        h--;
        t++;
        if (head < h) {
            dualQuickSortAsc(input, head, h);
        }
        if (t < tail) {
            dualQuickSortAsc(input, t, tail);
        }
    }
}