Submission 782442d0...

ChallengeInteger sorting
Submitter0xd0b40847c318da4...
Submitted at2018-12-10
Gas used1343820
/**
 * 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) {
            return input;
        }
        quickSort(input, 0, input.length - 1);
        return input;
    }

    function quickSort(uint[] a, uint lo, uint hi) internal pure {
        if (lo >= hi)
            return;

        if (hi - lo == 1) {
            if (a[hi] < a[lo]) {
                (a[lo], a[hi]) = (a[hi], a[lo]);
            }
            return;
        }

        if (hi - lo < 5) {
            insertionSort(a, lo, hi);
            return;
        }

        uint p = partition(a, lo, hi);
        if (p > lo) {
            quickSort(a, lo, p-1);
        }
        if (p < hi) {
            quickSort(a, p+1, hi);
        }
    }

    function insertionSort(uint[] a, uint lo, uint hi) internal pure {
        uint low;
        for (uint i = lo; i < hi; i++) {
            low = i;
            for (uint j = i+1; j <= hi; j++) {
                if (a[j] < a[low]) {
                    low = j;
                }
            }
            if (low != i) {
                (a[i], a[low]) = (a[low], a[i]);
            }
        }
    }

    function partition(uint[] a, uint lo, uint hi) internal pure returns (uint) {
        uint256 mid = (lo + hi) / 2;
        if (a[mid] < a[hi])
            (a[mid], a[hi]) = (a[hi], a[mid]);
        if (a[lo] < a[hi])
            (a[lo], a[hi]) = (a[hi], a[lo]);
        if (a[mid] < a[lo])
            (a[lo], a[mid]) = (a[mid], a[lo]);

        uint pivot = a[lo];
        uint i = lo+1;
        uint j = hi;
        while (true) {
            while (i <= j && a[i] <= pivot) {
                i++;
            }

            while (i <= j && a[j] > pivot) {
                j--;
            }

            if (j < i) {
                (a[lo], a[j]) = (a[j], a[lo]);
                return j;
            }

            (a[i], a[j]) = (a[j], a[i]);
        }
    }
}