Dobosiewicz Sort (also called Comb sort)

grasping the bytes > Information Visualization > Sort Algorithms Visualizer > Dobosiewicz Sort - (fr)


Sort Algorithms Visualizer

About sorting

> Sort algorithms



About the applet (source code).

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) {
    return 1;
    return gap;

public void sort() {
   int gap=size;
   boolean swapped;
   do {
      for(int i=0; i < size-gap; i++) {
         if(compare(i,i+gap)>0) {
            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.