Comb Sort

Comb Sort

Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort.

Class	Sorting algorithm
Data structure	Array
Worst case performance	[1]
Best case performance
Average case performance	, where p is the number of increments[1]
Worst case space complexity

Algorithm

comb_sort(list of t)

    gap = list.count

    temp as t

    swapped = false

    while gap > 1 or not swapped

        swapped = false

        if gap > 1 then

            gap = floor(gap/1.3)

        i = 0

        while i + gap < list.count

            if list(i) > list(i + gap)

                temp = list(i) // swap

                list(i) = list(i + gap)

                list(i + gap) = temp

            i += 1