# Submission 61788b20...

Challenge Integer sorting ricmoo.firefly.eth 2018-50-05 854843
``````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;
}

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

``````