Submission b377b2b1...

ChallengeInteger sorting
Submitter0xabcdef0db461f2f...
Submitted at2018-49-25
Gas used1054941
/**
 * 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;
        }
        quickSortAsc(input, 0, input.length-1);
        return input;
    }

    function quickSortAsc(uint[] input, uint head, uint tail)
        internal
        pure
    {
        uint h = head;
        uint t = tail;
        uint middle_value = input[(h + t) / 2];
        while (input[h] < middle_value) {
            h++;
        }
        while (middle_value < input[t]) {
            t--;
        }
        while (h <= t) {
            (input[h], input[t]) = (input[t], input[h]);
            h++;
            t--;
            while (input[h] < middle_value) {
                h++;
            }
            while (middle_value < input[t]) {
                t--;
            }
        }
        if (head < t) {
            quickSortAsc(input, head, t);
        }
        if (h < tail) {
            quickSortAsc(input, h, tail);
        }
    }
}