Comb Sort

Less known than others presented here sorting algorithms, but quite interesting one for how it pre-processes the data. Comb Sort is basically an improved bubble sort, which allows it to run in O(n log n) time in average cases. Unfortunately, the worst case is still O(n²).

The main idea behind the Comb Sort is to pre-process array, so the large values goes towards the end of the given array. The pre-process phase has multiple passes and number of them depends on how large the array to be sorted is. After pre-processing is finished in the second phase, we just run the Bubble Sort algorithm. Because the phase one has had taken care of moving part of items towards the end of the array, second phase doesn’t run so many iterations anymore. So as I said before the average cases is much faster than normal Bubble Sort.

There are two main phases in this algorithm:

Phase 1: Pick up a step size. This is the distance between items in the array, that you will be comparing. Step size can be any arbitrary number, but the best performance is achieved when the step starts with a value of the length of the array divided by 1.3.

Now you start from the end of the array comparing always two items, which are located from each other in the distance of the step. I.e. if we have an array to sort = [4, 3, 2, 1, -2, 0], and the first step would be equal to 3. In the first iteration we would compare values 0 and 2. 0 is smaller than 2, so we swap the items, and our array now looks like that: [4, 3, 0, 1, -2, 2]. We carry on going towards the front of the array, until we reach a place where first swap happened. In our example it would be index 2.

We repeat going through the array, each time dividing the step by our arbitrary constant (1.3), until the equals to 1. At which point we stop the phase 1.

Phase 2: Now we perform old fashioned bubble sort. Having the array pre-processed by “combing” phase, bubble sort doesn’t have to go so many times through it as it would normally. To increase the performance of the algorithm slightly more, provided implementation for the bubble sort here has got a flag, which will cause to stop iterating through the array if we detect that array is already sorted.

Pseudo code for comb sort:

# phase 1
for each_step
  for each_item in length of (array - step)
    if each_item is less than value of step index
      swap items

# phase 2
// perform bubble sort

Possible implementation in python:

def comb_sort(array):
    # phase 1
    step = int(len(array) / 1.3)
    while step > 1:
        for reverse_index in range(len(array) - 1, step - 1, -1):
            k = reverse_index - step
            if array[reverse_index] < array[k]:
                tmp = array[k]
                array[k] = array[reverse_index]
                array[reverse_index] = tmp
        step = int(step / 1.3)

    # phase 2
    again = True
    for index in range(len(array)):
        if again:
            again = False
            for index2 in range(len(array) - 1, index, -1):
                if array[index2] < array[index2 - 1]:
                    tmp = array[index2]
                    array[index2] = array[index2 - 1]
                    array[index2 - 1] = tmp
                    again = True
    return array