Quick sort in Solidity for Ethereum network

QuickSort.sol

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)]);
                i++;
                j--;
            }
        }
        if (left < j)
            quickSort(arr, left, j);
        if (i < right)
            quickSort(arr, i, right);
    }
}

@Ipseeta you can refer to this, https://gist.github.com/sdelvalle57/f5f65a31150ea9321f081630b416ed99

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

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

Is there any descending implementation of quicksort in solidity?

@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.

@ebulku , Sort the Array and Reverse it.

@ebulku , Sort the Array and Reverse it.

I commented this years ago, and there is a simple one during quicksort: https://stackoverflow.com/questions/64661313/descending-quicksort-in-solidity

what do left and right mean in that context?

what do left and right mean in that context?

The left and right pointers pointing to the array elements.

I've implemented a bubble sort: https://gist.github.com/gsscoder/24e09900a30c7c057bbd5bc2dfb9219f

This can help possibly

contract QuickSort {
    function quickSort(uint[] memory arr) public pure returns (uint[] memory) {
        if (arr.length <= 1) {
            return arr;
        }

        quickSortImpl(arr, 0, int(arr.length - 1));
        return arr;
    }

    function quickSortImpl(uint[] memory arr, int left, int right) private pure {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);

            if (pivotIndex > 1) {
                quickSortImpl(arr, left, pivotIndex - 1);
            }

            if (pivotIndex + 1 < right) {
                quickSortImpl(arr, pivotIndex + 1, right);
            }
        }
    }

    function partition(uint[] memory arr, int left, int right) private pure returns (int) {
        uint pivot = arr[uint(right)];
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (arr[uint(j)] <= pivot) {
                i++;
                (arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
            }
        }

        (arr[uint(i + 1)], arr[uint(right)]) = (arr[uint(right)], arr[uint(i + 1)]);
        return i + 1;
    }

}

This takes 350K gas with 100 elements