Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Quick sort in Solidity for Ethereum network
pragma solidity ^0.4.18;
contract QuickSort {
function sort(uint[] data) public constant returns(uint[]) {
quickSort(data, int(0), int(data.length - 1));
return data;
function quickSort(uint[] memory arr, int left, int right) internal{
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)]);
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
Copy link

Ipseeta commented Jan 24, 2018

Is there any efficient way to sort apart from quicksort?

Copy link

subhodi commented May 29, 2018

@Ipseeta there are some efficient sorting algorithms but i doubt Solidity implementations of such.

Copy link

sdelvalle57 commented Jun 2, 2018

Copy link

0xAshish commented Sep 19, 2018

@sdelvalle57 seriously bubble sort O(n*n) over quick sort O(nlogn) ?
merge sort, i can still consider.

Copy link

huyhoangk50 commented Nov 22, 2018

@0xAshish merge sort uses a lot of extra memory. Will that cost a lot of gas.

Copy link

ebulku commented Nov 3, 2020

Is there any descending implementation of quicksort in solidity?

Copy link

ASAPSegfault commented Oct 30, 2021

@0xAshish @huyhoangk50
The authors of this paper studied gas price and runtime of quick sort, merge sort and bubble sort algorithms on a Ganache private blockchain. Their results tells us that, among those, quick sort algorithm is best fitted to Ethereum.

Of course, this is not the main net, and a lot of things depends on their configuration of Ganache's chain and of their implementation of sorting algorithms themselves, but the information is, in my opinion, still useful to get an overview.

You may also want to check this thread.

Copy link

iSumitBanik commented Mar 28, 2022

@ebulku , Sort the Array and Reverse it.

Copy link

ebulku commented Apr 4, 2022

@ebulku , Sort the Array and Reverse it.

I commented this years ago, and there is a simple one during quicksort:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment