private void divide ( int [ ] idx , double [ ] data , ArrayList < int [ ] > ret , int start , int end , int depth ) { if ( depth == 0 ) { int [ ] a = Arrays . copyOfRange ( idx , start , end ) ; Arrays . sort ( a ) ; ret . add ( a ) ; return ; } final int count = end - start ; if ( count == 0 ) { // Corner case, that should barely happen. But for ties, we currently // Do not yet assure that it doesn't happen! for ( int j = 1 << depth ; j > 0 ; -- j ) { ret . add ( new int [ 0 ] ) ; } return ; } double m = 0. ; for ( int i = start ; i < end ; i ++ ) { m += data [ i ] ; } m /= count ; int pos = Arrays . binarySearch ( data , start , end , m ) ; if ( pos >= 0 ) { // Ties: try to choose the most central element. final int opt = ( start + end ) >> 1 ; while ( data [ pos ] == m ) { if ( pos < opt ) { pos ++ ; } else if ( pos > opt ) { pos -- ; } else { break ; } } } else { pos = ( - pos - 1 ) ; } divide ( idx , data , ret , start , pos , depth - 1 ) ; divide ( idx , data , ret , pos , end , depth - 1 ) ; }
Recursive call to further subdivide the array .