# Sorting an Array of integer with Ethereum

I'm trying to have a simple array of integer sorted in Solidity but i couldn't find any real ressources so instead i'm trying to do it "the hard way" but so far with very little success.

Is anyone aware of anything that could help ?

This is what i've tried so far , but with no luck. Whenever i try it i'm getting out of memory errors.

``````  function quickSort(uint[] arr, uint left, uint right) private returns(uint[] _arr){
uint i = left;
uint j = right;
uint tmp;
uint pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
``````

Anyone got something to share ?

Error is often " ERROR: invalid jump destination (PUSH1) "

Edit :

Same with :

``````function insertionSort(uint[] a){
for (uint i = 1;i < a.length;i++){
uint temp = a[i];
uint j;
for (j = i -1; j >= 0 && temp < a[j]; j--)
a[j+1] = a[j];
a[j + 1] = temp;
}
}
``````

edit 2 :

Fixed aswell

``````  function insertionSort(uint[] a)internal {
for (uint i = 1;i < a.length;i++){
uint temp = a[i];
uint j;
for (j = i -1; j >= 0 && temp < a[j]; j--)
a[j+1] = a[j];
a[j + 1] = temp;
}
}
``````

"Invalid jump destination" is generated when you access an array out of bounds. Did you try debugging it in mix?

The following code seems to work. By using the keyword `storage` in the argument type you can pass a storage reference (only works for internal functions and libraries), otherwise the storage data would be copied to memory. As an optimization you might consider copying the storage array to memory, checking whether it is sorted, if not, sort it and copy it back to storage. Another potential pitfall concerning browser-solidity: You have to enter array arguments as `[1,7,4,5]`.

Oh and the best optimization is of course to sort the array off-chain and only check on-chain whether it is sorted or not.

``````// SPDX-License-Identifier: MIT
pragma solidity ^0.7.0;

function quickSort(uint[] memory arr, int left, int right) pure {
int i = left;
int j = right;
if (i == j) return;
uint pivot = arr[uint(left + (right - left) / 2)];
while (i <= j) {
while (arr[uint(i)] < pivot) i++;
while (pivot < arr[uint(j)]) j--;
if (i <= j) {
(arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
i++;
j--;
}
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}

contract QuickSort {
function sort(uint[] memory data) public pure returns (uint[] memory) {
quickSort(data, int(0), int(data.length - 1));
return data;
}
}
``````

Edit (2020-10): Underflow problem fixed by @subhodi and updated to latest Solidity version.

• So there is no better way of sorting int arrays? – Joël Feb 20 '16 at 2:18
• I've tried but as soon as i'm trying to create a transaction for the method which call the fonction i get Solidity exception(Bad Jump). I've tried with your web tool aswell and on my devchain but i'm kind of stuck. Are there restriction of access to array stored? – user697 Feb 20 '16 at 2:41
• @user697 How much gas are you sending in your transaction? Start with 3,000,000 gas until things work, so that you avoid potential out of gas issues during development. – eth Feb 20 '16 at 5:25
• Doesn't work. I don't think it's an issue with gas tho, i'm never out of gas. I think it's something i didn't understood about accessing array in memory. Any of you successfully reproduced ? I'm using a public array of 5 unsorted number as parameter. – user697 Feb 20 '16 at 15:32
• Quicksort is O(log^2 n). with respect to size. Since size costs more than computation perhaps Heapsort would be better. The Wikipedia article notes that heapsort is used in small embedded systems, and you can consider the EVM a small embedded system. You should at least try it – Paul S Feb 22 '16 at 4:17

Quicksort algorithm without any VM exception: refer this gist https://gist.github.com/subhodi/b3b86cc13ad2636420963e692a4d896f

``````tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
``````

When j=0 and j-- leads to large integer value stored in j's memory this is because j is of type uint(unsigned integer) and 0-1=-1 (j--) which j cannot store so j's value will be (2^256)-1. In the next loop when EVM reads arr[j], it reads garbage value leading to exception.

Chriseth's solution looks good and clean and would work in an implementation using signed ints instead of unsigned ones. However you would need to change the line

``````j--;
``````

to

``````if (j > 0)  j--;
``````

if you want to avoid getting an integer underflow.

Subhod's answer above is good, but for variety's sake, here's a version I wrote that avoids `int`s entirely and keeps everything `uint`s. I've kicked the tires a bit but you should test further before deploying it. Also of course, as Nick Johnson noted on Twitter, quicksort's worst case is slow (O(n^2)) so you might want to find a faster O(n log n) one.

``````function sort(uint[] memory arr) public pure {
if (arr.length > 0)
quickSort(arr, 0, arr.length - 1);
}

function quickSort(uint[] memory arr, uint left, uint right) public pure {
if (left >= right)
return;
uint p = arr[(left + right) / 2];   // p = the pivot element
uint i = left;
uint j = right;
while (i < j) {
while (arr[i] < p) ++i;
while (arr[j] > p) --j;         // arr[j] > p means p still to the left, so j > 0
if (arr[i] > arr[j])
(arr[i], arr[j]) = (arr[j], arr[i]);
else
++i;
}

// Note --j was only done when a[j] > p.  So we know: a[j] == p, a[<j] <= p, a[>j] > p
if (j > left)
quickSort(arr, left, j - 1);    // j > left, so j > 0
quickSort(arr, j + 1, right);
}
``````

The problem with your code is that you are passing an `in-memory` array to recursive invocation. The array is being passed by copy (different instances on every invocation) instead of by reference (the same array).

The solution from @chriseth is correct because it uses `storage` which is passed by reference. This approach if unfortunately very costly as it demands to modify contract storage which is the most expensive EVM operation.

The best approach is to use quickSort to sort data in memory. You may achieve by eliminating the recurrence from the code and replacing it with an explicit stack.

``````function sort(uint[] storage data) {

uint n = data.length;
uint[] memory arr = new uint[](n);
uint i;

for(i=0; i<n; i++) {
arr[i] = data[i];
}

uint[] memory stack = new uint[](n+2);

//Push initial lower and higher bound
uint top = 1;
stack[top] = 0;
top = top + 1;
stack[top] = n-1;

//Keep popping from stack while is not empty
while (top > 0) {

uint h = stack[top];
top = top - 1;
uint l = stack[top];
top = top - 1;

i = l;
uint x = arr[h];

for(uint j=l; j<h; j++){
if  (arr[j] <= x) {
//Move smaller element
(arr[i], arr[j]) = (arr[j],arr[i]);
i = i + 1;
}
}
(arr[i], arr[h]) = (arr[h],arr[i]);
uint p = i;

//Push left side to stack
if (p > l + 1) {
top = top + 1;
stack[top] = l;
top = top + 1;
stack[top] = p - 1;
}

//Push right side to stack
if (p+1 < h) {
top = top + 1;
stack[top] = p + 1;
top = top + 1;
stack[top] = h;
}
}

for(i=0; i<n; i++) {
data[i] = arr[i];
}
}
``````

If you are interested in `gas consumption` by different sorting algorithms in solidity you may take a look at this repo.

• Just tested your code and it consumes more gas then example with `storage` writes. For instance, only initial and final copying consumes ~1.2kk gas. – Alex G.P. May 7 '18 at 16:11
``````function sort_array(uint64[] arr_) returns (uint64 [] )
{
uint256 l = arr_.length;
uint64[] memory arr = new uint64[] (l);

for(uint i=0;i<l;i++)
{
arr[i] = arr_[i];
}

for(i =0;i<l;i++)
{
for(uint j =i+1;j<l;j++)
{
if(arr[i]<arr[j])
{
uint64 temp= arr[j];
arr[j]=arr[i];
arr[i] = temp;

}

}
}

return arr;
}
``````