Submission 4e0539b5...

ChallengeInteger sorting
Submitter0x00f9474f1f603de...
Submitted at2018-40-08
Gas used852720
/**
 * 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 > 1) {
            quicksort(input, 0, input.length - 1);
        }
        return input;
    }

    function quicksort(uint[] input, uint lo, uint hi) public pure {
        if (hi - lo > 8) {
            uint pivot = input[(hi + lo) / 2];
            uint i = lo - 1;
            uint j = hi + 1;
            while(true) {
                do {
                    ++i;
                }
                while (input[i] < pivot);

                do {
                    --j;
                }
                while (input[j] > pivot);

                if (i >= j) {
                    break;
                }
                (input[i], input[j]) = (input[j], input[i]);
            }
            quicksort(input, lo, j);
            quicksort(input, j + 1, hi);
        }
        else {
            //insertion sort
            for (i = lo + 1; hi >= i; ++i) {
                pivot = input[i];
                j = i;
                while (j != 0) {
                    uint a = input[j-1];
                    if (a <= pivot) {
                        break;
                    }
                    input[j--] = a;
                }
                input[j] = pivot;
            }
        }
    }

    function partition(uint[] input, uint lo, uint hi) public pure returns(uint) {
        uint pivot = input[(hi + lo) / 2];
        uint i = lo - 1;
        uint j = hi + 1;
        while(true) {
            do {
                ++i;
            }
            while (input[i] < pivot);

            do {
                --j;
            }
            while (input[j] > pivot);

            if (i >= j) {
                return j;
            }
            (input[i], input[j]) = (input[j], input[i]);
        }
    }
}