sorting networks for up to 64 inputs. the fastest way to sort small lists.
Near-optimal sorting networks for up to 64 inputs based on work by bertdobbelaere and Ariya Hidayat /
Bei Zhang
sort function falls back to TimSort if list is longer than 64.
By default, performs an in-place, ascending sort, but you can change how it works.
also includes tool for creating superfast hard-coded sorting functions in js.
``sh`
npm i sorting-networks
`javascript`
var NetworkSort = require('sorting-networks').sort;
var row = [5,4,3,999,0];
console.log(NetworkSort(row));
//[ 0, 3, 4, 5, 999 ]
benchmark test vs Array.sort, TimSort, FastSort for 1M random short lists
`javascript
var NetworkSort = require('sorting-networks').sort;
var TimSort = require('timsort').sort;
var FastSort = require('fast-sort').sort;
//generating random lists of numbers...
var numberOfEntries = 999999;
var entriesList = [];
for(var i=0;i
var lengthOfEntry = Math.floor(2+60*Math.random());
for(var j=0;j
}
entriesList.push(row);
}
var t0=Date.now();
function numberCompare(a,b) {return a-b;}
for(var i=0;i
NetworkSort(row) //1214ms
//TimSort(row, numberCompare); //1354ms
//row = FastSort(row).asc(); //2908ms
//row.sort(); //3413ms
}
console.log('took',Date.now()-t0);
`
Sort one list using the values from another.
`javascript
var NetworkSort = require('sorting-networks').sort_byProxy;
var listToBeSorted = [1,2,3,4,5]; //eg indices of some objects
var listToSortWith = [9,8,7,6,5] //eg values to compare to do sorting
var res = NetworkSort(listToBeSorted, listToSortWith)
//[ 5, 4, 3, 2, 1 ]
`
Note: unlike the regular sort, proxy sort only sorts up to length 64, there is no fallback for longer lists.
You can generate hardcoded sort functions which will run as much as 2x faster than the generic function included here, but take up a lot of space/code.
If you are sorting integers, you can optionally employ xor swaps.
`javascript
var sn = require('sorting-networks');
var networkSize = 4; //number of inputs to sort [up to 64]
var isAscending = true; //default true
var useXorSwaps = true; //swap using XOR instead of intermediate variable
var functionString = sn.generateJsSortFunction(networkSize, isAscending, useXorSwaps);
console.log(functionString);
//resulting string
function sort4(a){
if(a[0]>a[2]){a[0]^=a[2]^(a[2]=a[0]);}
if(a[1]>a[3]){a[1]^=a[3]^(a[3]=a[1]);}
if(a[0]>a[1]){a[0]^=a[1]^(a[1]=a[0]);}
if(a[2]>a[3]){a[2]^=a[3]^(a[3]=a[2]);}
if(a[1]>a[2]){a[1]^=a[2]^(a[2]=a[1]);}
return a;
}
//resulting string with xorSwaps = false
function sort4(a){
if(a[0]>a[2]){t=a[2];a[2]=a[0];a[0]=t;}
if(a[1]>a[3]){t=a[3];a[3]=a[1];a[1]=t;}
if(a[0]>a[1]){t=a[1];a[1]=a[0];a[0]=t;}
if(a[2]>a[3]){t=a[3];a[3]=a[2];a[2]=t;}
if(a[1]>a[2]){t=a[2];a[2]=a[1];a[1]=t;}
return a;
}
//benchmark -- sorting 1M length-16 lists using hardcoded XOR swaps...
//sort16(row); //184ms
//NetworkSort(row) //383ms
//TimSort(row, numberCompare); //474ms
//row = FastSort(row).asc(); //1181ms
//row.sort(); //1328ms
`
See a huge list of resulting hardcoded sorting network functions here.
If you are using integers, see the versions with XOR swaps.
These are not included directly in this library in order to save space.
Make sure to run your own benchmarks to see what runs fastest for you!
Example of "manually" sorting 16 numbers using a 16-input network.
`javascript
//get the serialized network...
var theNetwork = require('sorting-networks').networks[16]; //networks[x] = data for network with x inputs (x in range 2...64)
//https://ariya.io/2013/10/sorting-networks-using-higher-order-functions-of-javascript-array
function compareswap(array, p, q) { //ascending
if (array[p] > array[q]) {
var temp = array[q];
array[q] = array[p];
array[p] = temp;
}
}
function sort(network, entries) {
var l = network.length;
for (var i = 0; i < l; i+=2){
compareswap(entries, network[i], network[i+1])
}
}
var listToSort = [4,3,2,1,5];
sort(theNetwork, listToSort);
console.log(listToSort); //[1,2,3,4,5]
``
