Submission 077ff632...

ChallengeInteger sorting
Submitterhyszeth.eth
Submitted at2018-37-30
Gas used653513
/**
 * 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/
 *
 * Author: Greg Hysen (@hysz)
 * Date: June, 2018
 */

pragma solidity 0.4.24;

contract Sort {

    event RemoveBeforeSubmission(uint i);

    /**
     * @dev Sorts a list of integers in ascending order.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */
     function sort(uint[] input)
      public
      pure
      returns(uint[])
    {
        if(input.length == 0) return input;
        quickSort(input, 0, input.length - 1, input[0], input[input.length - 1]);
        return input;
     }

        function quickSort(
            uint[] input,
            uint lo,
            uint hi,
            uint loElem,
            uint hiElem
        )
         internal
         pure
        {
            // Pivot (Median of 3)
            uint i = uint((hi+lo)/2); // pivot index
            uint pivot = input[i];
            if(loElem >= pivot) { // [pivot, loElem] [hiElem]
                if(loElem <= hiElem) {
                    // [pivot, loElem, hiElem]
                    // Only swap pivot and loElem
                    input[lo] = pivot;
                    input[i] = loElem;
                    (loElem, pivot) = (pivot, loElem);
                } else {
                    // [pivot, hiElem, loElem] or [hiElem, pivot, loElem]
                    if(hiElem >= pivot) {
                        // [pivot, hiElem, loElem]
                        input[lo] = pivot;
                        input[i] = hiElem;
                        input[hi] = loElem;
                        (loElem, pivot, hiElem) = (pivot, hiElem, loElem);
                    } else {
                        // [hiElem, pivot, loElem]
                        input[lo] = hiElem;
                        input[hi] = loElem;
                        (loElem, hiElem) = (hiElem, loElem);
                    }
                }
            } else {// if(loElem < pivot) { // [loElem, pivot] [hiElem]
                if(pivot >= hiElem) {
                    // [loElem, hiElem, pivot] or [hiElem, loElem, pivot]
                    if(hiElem >= loElem) {
                        // [loElem, hiElem, pivot]
                        input[i] = hiElem;
                        input[hi] = pivot;
                        (pivot, hiElem) = (hiElem, pivot);
                    } else {
                        // [hiElem, loElem, pivot]
                        input[lo] = hiElem;
                        input[i] =  loElem;
                        input[hi] = pivot;
                        (loElem, pivot, hiElem) = (hiElem, loElem, pivot);
                    }
                } else {
                    // [loElem, pivot, hiElem]
                    // Do nothing
                }
            }

            // Hoare pivot algorithm
            // Note we skip the lo/hi elements because
            // we already know they're in the correct position.
            uint iElem;
            uint jElem;
            i = lo;
            uint j = hi;
            while(true) {
                while((iElem=input[uint(++i)]) <= pivot) {}
                while((jElem=input[uint(--j)]) >= pivot) {}

                if(i >= j) {
                    // Sort
                    if(j - lo <= 7) insertionSort(input, lo, j);
                    else            quickSort(input, lo, j, loElem, jElem);

                    if(hi - i <= 7) return insertionSort(input, i, hi);
                                    return  quickSort(input, i, hi, iElem, hiElem);
                }
                input[uint(i)] = jElem;
                input[uint(j)] = iElem;
            }
        }

        function insertionSort(uint[] input, uint lo, uint hi)
            private
            pure
        {
            // Base case
            if(lo == hi++) return;

            // If within threshold, run insertion sort instead.



            uint a = input[lo];
            uint i = lo + 1;
            // 1
            uint b = input[i];
                if(a > b) {
                    (a, b) = (b, a);
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                return;
            }

            // 2
            uint c = input[i];
                if(b > c) {
                    (b, c) = (c, b);
                    if(a > b) {
                        (a, b) = (b, a);
                    }
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                input[lo++] = c;
                return;
            }

            // 3
            uint d = input[i];
                if(c > d) {
                    (c, d) = (d, c);
                    if(b > c) {
                        (b, c) = (c, b);
                        if(a > b) {
                            (a, b) = (b, a);
                        }
                    }
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                input[lo++] = c;
                input[lo++] = d;
                return;
            }

            // 4
            uint e = input[i];
                if(d > e) {
                    (d, e) = (e, d);
                    if(c > d) {
                        (c, d) = (d, c);
                        if(b > c) {
                            (b, c) = (c, b);
                            if(a > b) {
                                (a, b) = (b, a);
                            }
                        }
                    }
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                input[lo++] = c;
                input[lo++] = d;
                input[lo++] = e;
                return;
            }

            // 5
            uint f = input[i];
                if(e > f) {
                    (e, f) = (f, e);
                    if(d > e) {
                        (d, e) = (e, d);
                        if(c > d) {
                            (c, d) = (d, c);
                            if(b > c) {
                                (b, c) = (c, b);
                                if(a > b) {
                                    (a, b) = (b, a);
                                }
                            }
                        }
                    }
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                input[lo++] = c;
                input[lo++] = d;
                input[lo++] = e;
                input[lo++] = f;
                return;
            }

            // 6
            uint g = input[i];
                if(f > g) {
                    (f, g) = (g, f);
                    if(e > f) {
                        (e, f) = (f, e);
                        if(d > e) {
                            (d, e) = (e, d);
                            if(c > d) {
                                (c, d) = (d, c);
                                if(b > c) {
                                    (b, c) = (c, b);
                                    if(a > b) {
                                        (a, b) = (b, a);
                                    }
                                }
                            }
                        }
                    }
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                input[lo++] = c;
                input[lo++] = d;
                input[lo++] = e;
                input[lo++] = f;
                input[lo++] = g;
                return;
            }

            // 7
            uint h = input[i];
                if(g > h) {
                    (g, h) = (h, g);
                    if(f > g) {
                        (f, g) = (g, f);
                        if(e > f) {
                            (e, f) = (f, e);
                            if(d > e) {
                                (d, e) = (e, d);
                                if(c > d) {
                                    (c, d) = (d, c);
                                    if(b > c) {
                                        (b, c) = (c, b);
                                        if(a > b) {
                                            (a, b) = (b, a);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            if(++i == hi) {
                input[lo++] = a;
                input[lo++] = b;
                input[lo++] = c;
                input[lo++] = d;
                input[lo++] = e;
                input[lo++] = f;
                input[lo++] = g;
                input[lo++] = h;
                return;
            }
        }
}