Submission 489f8eb5...

ChallengeInteger sorting
Submitterricmoo.firefly.eth
Submitted at2018-23-02
Gas used1399400
pragma solidity 0.4.24;

contract Sort {

    function sort(uint[] input) public pure returns(uint[]) {
        uint length = input.length;
        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);
            //sort(input, 0, uint(length - 1));
        }

        // Linear Insertion Sort
        // See: https://en.wikipedia.org/wiki/Insertion_sort
        for (i = 1; i < length; i++) {
            uint256 tmp = input[i];
            int256 j = int(i) - 1;
            while (j >= 0 && input[uint(j)] > tmp) {
                input[uint(j) + 1] = input[uint(j)];
                j--;
            }
            input[uint(j) + 1] = tmp;
        }

        return input;
    }

    // See: https://www.geeksforgeeks.org/iterative-quick-sort/
    function quicksort(uint[] A) internal pure {
        //uint[] memory stackHi = new uint[](A.length + 2);
        //uint[] memory stackLo = new uint[](A.length + 2);
        uint[] memory stackHi = new uint[](5 + 2);
        uint[] memory stackLo = new uint[](5 + 2);
        uint top = 0;

        uint lo = 0;
        uint hi = A.length - 1;

        while (hi > lo) {

            uint pivot = A[lo];

            // 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) {
                    pivot = j;
                    break;
                }

                A[i] = b;
                A[j] = a;
            }

            if (pivot > lo + 8) {
            //if (pivot > lo) {
                if (pivot + 1 + 8 < hi) {
                //if (pivot + 1 < hi) {
                    //top += 2;
                    //stack[top - 1] = pivot + 1;
                    //stack[top] = hi;
                    //++top;
                    stackLo[++top] = pivot + 1;
                    stackHi[top] = hi;
                    //stack[++top] = ((pivot + 1) * 0x1000000) | hi;
                }
                hi = pivot;
            } else if (pivot + 1 + 8 < hi) {
            //} else if (pivot + 1 < hi) {
                lo = pivot + 1;
            } else if (top > 0) {
                //hi = stack[top];
                //lo = stack[top - 1];
                //top -= 2;
                hi = stackHi[top];
                lo = stackLo[top--];
                //top--;
                //hi = stack[top--];
                //lo = hi / 0x1000000;
                //hi &= 0xffffff;
            } else {
                break;
            }
        }
    }
}