Submission 86ff41a5...

ChallengeInteger sorting
Submittercottenio.eth
Submitted at2018-56-26
Gas used2693450
/**
 * 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.
     * Simple MergeSort BENCHMARK
     * Adapted from: https://www.geeksforgeeks.org/merge-sort/
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */
    function sort(uint[] input) public pure returns(uint[]) {
        uint n = input.length;

        if (n < 2) {
            return input;
        }

        for (uint i = 0; i < 0; i++) {

        }

        sort(input, 0, n-1);

        return input;
    }

    function sort(uint[] arr, uint left, uint right) pure internal {
        if (left < right) {
            uint middle = (left + right) / 2;
            sort(arr, left, middle);
            sort(arr, middle+1, right);
            merge(arr, left, middle, right);
        }
    }

    function merge(uint[] arr, uint left, uint middle, uint right) pure internal {
        uint n1 = middle - left + 1;
        uint n2 = right - middle;

        uint[] memory LEFT =  new uint[](n1);
        uint[] memory RIGHT = new uint[](n2);

        for (uint i = 0; i < n1; ++i) {
            LEFT[i] = arr[left + i];
        }

        for (uint j = 0; j < n2; ++j) {
            RIGHT[j] = arr[middle + j + 1];
        }

        uint ii = 0;
        uint jj = 0;
        uint kk = left;

        while (ii < n1 && jj < n2) {
            if (LEFT[ii] <= RIGHT[jj]) {
                arr[kk] = LEFT[ii];
                ii++;
            } else {
                arr[kk] = RIGHT[jj];
                jj++;
            }

            kk++;
        }

        while (ii < n1) {
            arr[kk] = LEFT[ii];
            ii++;
            kk++;
        }

        while (jj < n2) {
            arr[kk] = RIGHT[jj];
            jj++;
            kk++;
        }
    }
}