Submission cb542a74...

ChallengeInteger sorting
Submitter0xabcdef0db461f2f...
Submitted at2018-50-28
Gas used925682
/**
 * 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;
        }
        uint t = input.length - 1;
        sortTwoOrThree(input, 0, t);
        if (t < 3) {
            return input;
        }
        quickSortAsc(input, 0, t, input[t / 2]);
        return input;
    }

    function sortTwoOrThree(uint [] input, uint head, uint tail)
        internal
        pure
    {
        uint tmp = tail - head;
        if (tmp == 1) {
            if (input[head] > input[tail]) {
                (input[head], input[tail]) = (input[tail], input[head]);
            }
        } else {
            tmp = (head + tail) / 2;
            if (input[head] < input[tmp]) {
                if (input[tmp] < input[tail]) {
                } else {
                    if (input[head] < input[tail]) {
                        (input[tmp], input[tail]) = (input[tail], input[tmp]);
                    } else {
                        (input[head], input[tmp], input[tail]) = (input[tail], input[head], input[tmp]);
                    }
                }
            } else {
                if (input[tmp] < input[tail]) {
                    if (input[head] < input[tail]) {
                        (input[head], input[tmp]) = (input[tmp], input[head]);
                    } else {
                        (input[head], input[tmp], input[tail]) = (input[tmp], input[tail], input[head]);
                    }
                } else {
                    (input[head], input[tail]) = (input[tail], input[head]);
                }
            }
        }
    }

    function quickSortAsc(uint[] input, uint head, uint tail, uint mval)
        internal
        pure
    {
        uint tmp = tail - head;
        if (tmp < 3) {
            sortTwoOrThree(input, head, tail);
            return;
        } else if (tmp > 64) {
            sortTwoOrThree(input, head, tail);
        }
        uint h = head;
        uint t = tail;
        while (h <= t) {
            while (input[h] < mval) {
                h++;
            }
            while (mval < input[t]) {
                t--;
            }
            if (h <= t) {
                (input[h], input[t]) = (input[t], input[h]);
                h++;
                if (t > 0) {
                    t--;
                }
            }
        }
        if (head < t) {
            quickSortAsc(input, head, t, input[(head + t) / 2]);
        }
        if (h < tail) {
            quickSortAsc(input, h, tail, input[(h + tail) / 2]);
        }
    }
}