Submission 3f5e51a5...
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]);
//uint tmp = input[i];
//input[i] = input[length - i - 1];
//input[length - i - 1] = tmp;
}
asc = length - asc - 1;
}
// Already sorted
if ((asc + 1) == length) { return input; }
// If less than 16 things are already sorted...
// @TODO: Build testcases to find an imperical value that is good...
if (asc + 16 < length) {
/*
// Not needed anymore; mostly sorted lists are handled by linear insertion sort
// Fisher-Yates Shuffle
uint accum = 0xb7adaa22903e58e3f323d2f70f87e0eeb5d6447027b9f9eab9df7cbcab31f4e4;
for (uint i = length - 1; i > 1; i--) {
uint a = input[i];
accum ^= a;
uint j = accum % (i + 1);
input[i] = input[j];
input[j] = a;
}
*/
// QuickSort
sort(input, 0, uint(length - 1));
} else {
// 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;
}
// Quick Sort (Hoare partition scheme)
// See: https://en.wikipedia.org/wiki/Quicksort
function sort(uint[] A, uint lo, uint hi) internal pure {
if (lo < hi) {
uint p = partition(A, lo, hi);
sort(A, lo, p);
sort(A, p + 1, hi);
}
}
function partition(uint[] A, uint lo, uint hi) internal pure returns (uint) {
uint pivot = A[uint(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) {
while(true) {
i++;
if (A[uint(i)] >= pivot) { break; }
}
while(true) {
j--;
if (A[uint(j)] <= pivot) { break; }
}
if (i >= j) { return j; }
(A[uint(i)], A[uint(j)]) = (A[uint(j)], A[uint(i)]);
}
}
}