Submission 6d57fbc8...

ChallengeInteger sorting
Submitter0x888888417655103...
Submitted at2018-54-30
Gas used945698
pragma solidity 0.4.24;

contract Sort {

    function sort(
        uint[] input
    ) public pure returns(uint[]) {
        if (input.length == 0) { return; }
        quickSort(input);
        return input;
    }

    function insertSort(
        uint[] input,
        int head,
        int tail
    ) private pure {
        int j;
        uint tmp;
        for (uint i = uint(head)+1; i <= uint(tail); i++) {
            tmp = input[i];
            j = int(i - 1);
            for (; j >= head; j--) {
                if (tmp > input[uint(j)]) {
                    break;
                }
                input[uint(j)+1] = input[uint(j)];
            }
            input[uint(j)+1] = tmp;
        }
    }

    function quickSort(
        uint[] input
    ) private pure {
        int head;
        int h;
        int tail;
        int t;
        uint pivot;
        int[] memory stack = new int[](input.length+2);
        stack[1] = 0;
        stack[2] = int(input.length-1);
        uint ptr = 2;
        while (ptr > 0) {
            tail = stack[ptr--];
            head = stack[ptr--];
            h = head;
            t = tail;
            pivot = input[uint(h+t)/2];
            while (h <= t) {
                while (input[uint(h)] < pivot) { h += 1; }
                while (pivot < input[uint(t)]) { t -= 1; }
                if (h <= t) {
                    (input[uint(h++)], input[uint(t--)]) = (input[uint(t)], input[uint(h)]);
                }
            }
            if (head < t) {
                if (t - head <= 8) {
                    insertSort(input, head, t);
                } else {
                    stack[++ptr] = head;
                    stack[++ptr] = t;
                }
            }
            if (h < tail) {
                if (tail - h <= 8) {
                    insertSort(input, h, tail);
                } else {
                    stack[++ptr] = h;
                    stack[++ptr] = tail;
                }
            }
        }
    }
}