Submission 61788b20...

ChallengeInteger sorting
Submitterricmoo.firefly.eth
Submitted at2018-50-05
Gas used854843
pragma solidity 0.4.24;

contract Sort {

    function sort(uint[] input) public pure returns(uint[]) {
        uint length = input.length;

        // Trivial cases
        if (length <= 1) { return input; }

        uint i;

        // Count ordered elements
        uint asc = 0;
        for (i = length - 1; i > 0; i--) {
            if (input[i] >= input[i - 1]) { asc++; }
        }

        // If Almost entirely reversed, reverse it
        if (asc < (length / 4)) {
            uint end = length / 2;
            for (i = 0; i < end; i++) {
                (input[i], input[length - i - 1]) = (input[length - i - 1], input[i]);
            }
            asc = length - asc - 1;
        }

        // Already sorted
        if ((asc + 1) == length) { return input; }

        // QuickSort
        if (asc + 8 < length) {
            quicksort(input,0, length - 1);
        }

        // Linear Insertion Sort
        // See: https://en.wikipedia.org/wiki/Insertion_sort
        for (i = 1; i < length; i++) {
            uint256 tmp = input[i];
            uint256 j = i;
            while (j != 0) {
                asc = input[j - 1];
                if (asc <= tmp) { break; }
                input[j] = asc;
                j--;
            }
            input[j] = tmp;
        }

        return input;
    }

    // See: https://www.geeksforgeeks.org/iterative-quick-sort/
    function quicksort(uint[] A,uint lo, uint hi) internal pure {
        while (true) {

            uint pivot = A[(lo + hi) / 2];

            // Note: May temporarility overflow below 0, but will be corrected in the first loop
            uint i = lo - 1;
            uint j = hi + 1;
            while (true) {
                uint a;
                uint b;
                while(true) {
                    a = A[++i];
                    if (a >= pivot) { break; }
                }
                while(true) {
                    b = A[--j];
                    if (b <= pivot) { break; }
                }

                if (i >= j) {
                    break;
                }

                //if (a != b) {
                A[i] = b;
                A[j] = a;
                //}
            }

            //if (pivot > lo) {
            if (j > lo + 8) {
                //if (pivot + 1 + 8 < hi) {
                if (j + 1 + 8 < hi) {
                    quicksort(A, j + 1, hi);
                }
                hi = j;
            //} else if (pivot + 1 + 8 < hi) {
            } else if (j + 1 + 8  < hi) {
                lo = j + 1;
            } else {
                break;
            }
        }
    }
}