123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 |
- // Hybrid radix sort from
- // - https://gist.github.com/sciecode/93ed864dd77c5c8803c6a86698d68dab
- // - https://github.com/mrdoob/three.js/pull/27202#issuecomment-1817640271
- //
- // expects unsigned 32b integer values
- const POWER = 3;
- const BIT_MAX = 32;
- const BIN_BITS = 1 << POWER;
- const BIN_SIZE = 1 << BIN_BITS;
- const BIN_MAX = BIN_SIZE - 1;
- const ITERATIONS = BIT_MAX / BIN_BITS;
- const bins = new Array( ITERATIONS );
- const bins_buffer = new ArrayBuffer( ( ITERATIONS + 1 ) * BIN_SIZE * 4 );
- let c = 0;
- for ( let i = 0; i < ( ITERATIONS + 1 ); i ++ ) {
- bins[ i ] = new Uint32Array( bins_buffer, c, BIN_SIZE );
- c += BIN_SIZE * 4;
- }
- const defaultGet = ( el ) => el;
- export const radixSort = ( arr, opt ) => {
- const len = arr.length;
- const options = opt || {};
- const aux = options.aux || new arr.constructor( len );
- const get = options.get || defaultGet;
- const data = [ arr, aux ];
- let compare, accumulate, recurse;
- if ( options.reversed ) {
- compare = ( a, b ) => a < b;
- accumulate = ( bin ) => {
- for ( let j = BIN_SIZE - 2; j >= 0; j -- )
- bin[ j ] += bin[ j + 1 ];
- };
- recurse = ( cache, depth, start ) => {
- let prev = 0;
- for ( let j = BIN_MAX; j >= 0; j -- ) {
- const cur = cache[ j ], diff = cur - prev;
- if ( diff != 0 ) {
- if ( diff > 32 )
- radixSortBlock( depth + 1, start + prev, diff );
- else
- insertionSortBlock( depth + 1, start + prev, diff );
- prev = cur;
- }
- }
- };
- } else {
- compare = ( a, b ) => a > b;
- accumulate = ( bin ) => {
- for ( let j = 1; j < BIN_SIZE; j ++ )
- bin[ j ] += bin[ j - 1 ];
- };
- recurse = ( cache, depth, start ) => {
- let prev = 0;
- for ( let j = 0; j < BIN_SIZE; j ++ ) {
- const cur = cache[ j ], diff = cur - prev;
- if ( diff != 0 ) {
- if ( diff > 32 )
- radixSortBlock( depth + 1, start + prev, diff );
- else
- insertionSortBlock( depth + 1, start + prev, diff );
- prev = cur;
- }
- }
- };
- }
- const insertionSortBlock = ( depth, start, len ) => {
- const a = data[ depth & 1 ];
- const b = data[ ( depth + 1 ) & 1 ];
- for ( let j = start + 1; j < start + len; j ++ ) {
- const p = a[ j ], t = get( p ) >>> 0;
- let i = j;
- while ( i > start ) {
- if ( compare( get( a[ i - 1 ] ) >>> 0, t ) )
- a[ i ] = a[ -- i ];
- else
- break;
- }
- a[ i ] = p;
- }
- if ( ( depth & 1 ) == 1 ) {
- for ( let i = start; i < start + len; i ++ )
- b[ i ] = a[ i ];
- }
- };
- const radixSortBlock = ( depth, start, len ) => {
- const a = data[ depth & 1 ];
- const b = data[ ( depth + 1 ) & 1 ];
- const shift = ( 3 - depth ) << POWER;
- const end = start + len;
- const cache = bins[ depth ];
- const bin = bins[ depth + 1 ];
- bin.fill( 0 );
- for ( let j = start; j < end; j ++ )
- bin[ ( get( a[ j ] ) >>> shift ) & BIN_MAX ] ++;
- accumulate( bin );
- cache.set( bin );
- for ( let j = end - 1; j >= start; j -- )
- b[ start + -- bin[ ( get( a[ j ] ) >>> shift ) & BIN_MAX ] ] = a[ j ];
- if ( depth == ITERATIONS - 1 ) return;
- recurse( cache, depth, start );
- };
- radixSortBlock( 0, 0, len );
- };
|