src/sort/fordjohnson.js

 
export function _fordjohnson ( binarysearch ) {
 
	const fordjohnson = function ( compare , swap , a , i , j ) {
 
		var m , k , t , y , p , q , r , x , l , w , s , pairswap ;
 
		if ( j - i < 2 ) return ;
 
		k = m = ( j - i ) / 2 | 0 ;
 
		// compare pairs of elements and put largest elements at the front of the
		// array
 
		while ( k-- ) {
 
			if ( compare( a[i+k] , a[i+m+k] ) < 0 ) {
 
				swap( a , i + k , i + m + k ) ;
 
			}
 
		}
 
		// sort the largest elements at the front recursively
 
		pairswap = function ( a , i , j ) {
			swap( a , i , j ) ;
			swap( a , i + m , j + m ) ;
		} ;
 
		fordjohnson( compare , pairswap , a , i , i + m ) ;
 
		// merge the rest of the array into the front, one item at a time
 
		p = y = t = 1 ;
 
		q = 0 ;
 
		while ( i + m + t <= j ) {
 
			r = t ;
 
			while ( r --> q ) {
 
				w = a[i+m+t-1] ;
 
				x = binarysearch( compare , a , i , i + m + q , w ) ;
				l = x[0] + x[1] ;
 
				s = i + m + t ;
 
				while ( --s > l ) {
 
					swap( a , s , s - 1 ) ;
 
				}
 
			}
 
			q = t ;
 
			p *= 2 ;
			y = p - 2 * t ;
			t += y ;
 
		}
 
		r = j - i - m ;
 
		while ( r --> q ) {
 
			w = a[j-1] ;
 
			x = binarysearch( compare , a , i , i + m + q , w ) ;
			l = x[0] + x[1] ;
 
			s = j ;
 
			while ( --s > l ) {
 
				swap( a , s , s - 1 ) ;
 
			}
 
 
		}
 
	} ;
 
	return fordjohnson ;
 
}