static void introspectiveInsertionSort ( final int [ ] a , final int l , final int r ) { final int length = ( r - l ) + 1 ; long cost = 0 ; final long costLimit = 8L * length ; for ( int i = l + 1 ; i <= r ; i ++ ) { int j = i ; final long v = a [ i ] & 0XFFFF_FFFF L ; //v must be long while ( ( j >= ( l + 1 ) ) && ( v < ( ( a [ j - 1 ] ) & 0XFFFF_FFFF L ) ) ) { a [ j ] = a [ j - 1 ] ; j -= 1 ; } a [ j ] = ( int ) v ; cost += ( i - j ) ; // distance moved is a measure of work if ( cost > costLimit ) { //we need an unsigned sort, but it is linear time and very rarely occurs final long [ ] b = new long [ a . length ] ; for ( int m = 0 ; m < a . length ; m ++ ) { b [ m ] = a [ m ] & 0XFFFF_FFFF L ; } Arrays . sort ( b , l , r + 1 ) ; for ( int m = 0 ; m < a . length ; m ++ ) { a [ m ] = ( int ) b [ m ] ; } // The following sanity check can be used during development //int bad = 0; //for (int m = l; m < (r - 1); m++) { // final long b1 = a[m] & 0XFFFF_FFFFL; // final long b2 = a[m + 1] & 0XFFFF_FFFFL; // if (b1 > b2) { bad++; } //} //assert (bad == 0); return ; } } // The following sanity check can be used during development // int bad = 0; // for (int m = l; m < (r - 1); m++) { // final long b1 = a[m] & 0XFFFF_FFFFL; // final long b2 = a[m + 1] & 0XFFFF_FFFFL; // if (b1 > b2) { bad++; } // } // assert (bad == 0); }
In applications where the input array is already nearly sorted insertion sort runs in linear time with a very small constant . This introspective version of insertion sort protects against the quadratic cost of sorting bad input arrays . It keeps track of how much work has been done and if that exceeds a constant times the array length it switches to a different sorting algorithm .