Submission 4c1dca98...

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

    function findExtreme(uint[] input) internal pure {
        uint t = input.length - 1;
        if (input[0] > input[t]) {
            (input[0], input[t]) = (input[t], input[0]);
        }
        for (uint i = 1; i < t; i++) {
            if (input[i] < input[0]) {
                (input[0], input[i]) = (input[i], input[0]);
            } else if (input[i] > input[t]) {
                (input[t], input[i]) = (input[i], input[t]);
            }
        }
    }

    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 quickSortAsc(uint[] memory input, uint head, uint tail, uint mval) internal pure
    {
        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++;
                t--;
            }
        }
        if (head < t) {
            if (t - head <= 8) {
                insertSortAsc(input, head, t);
            } else {
                quickSortAsc(input, head, t, input[(head + t) / 2]);
            }
        }
        if (h < tail) {
            if (tail - h <= 8) {
                insertSortAsc(input, h, tail);
            } else {
                quickSortAsc(input, h, tail, input[(h + tail) / 2]);
                return;
            }
        }
    }
}