Invented by Dobosiewicz in 1980, it can be interpreted as a variant of Shell sort, as it replaces a sequence of decreasing-gap insertion sort with bubble sort passes. In other words, this algorithm does to bubble sort what Shell sort does to insertion sort. This algorithm and its variants (that include a shaker pass or a brick pass) are interesting to study from a theoretical standpoint, nevertheless, all its variants are less efficient than the best Shell sorts, which is in turn less efficient than a tuned quicksort (when there is no need for stability), or a tuned merge sort (when stability is required).
public class DoboSort extends SortAlgorithm {
public DoboSort (int t, MainView v) {
super("Brick Sort", t, v);
}
int reduce(int gap) {
gap=gap*10/13;
if(gap==9||gap==10)
gap=11;
if(gap<1)
return 1;
return gap;
}
public void sort() {
int gap=size;
boolean swapped;
do {
swapped=false;
gap=reduce(gap);
for(int i=0; i < size-gap; i++) {
if(compare(i,i+gap)>0) {
swapped=true;
exchange(i, i+gap);
}
}
} while(gap>1||swapped);
}
}
This algorithm is mentioned in this paper. Quite a few pages on the net, including Wikipedia, attribute this algorithm to Stephen Lacey and Richard Box, who described it in Byte Magazine in April 1991.