Submission 9c176410...

Challenge	Integer sorting
Submitter	ricmoo.firefly.eth
Submitted at	2018-35-05
Gas used	885336

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);
        }

        // 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 stackHi = 0;
        uint stackLo = 0;

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

        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) {
                    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) {
                    stackLo *= 0x10000;
                    stackLo |= pivot + 1;
                    stackHi *= 0x10000;
                    stackHi |= hi;
                }
                hi = pivot;
            } else if (pivot + 1 + 8 < hi) {
            //} else if (pivot + 1 < hi) {
                lo = pivot + 1;
            } else if (stackHi != 0) {
                hi = stackHi & 0xffff;
                stackHi /= 0x10000;
                lo = stackLo & 0xffff;
                stackLo /= 0x10000;
            } else {
                break;
            }

        }
    }
}