Do a gapped insertion sort for this gap size . The first gap elements a [ 0. . gap - 1 ] are already in gapped order keep adding one more element until the entire array is gap sorted
for ( int i = gap ; i < n ; i += 1 ) {