Cocktail sort is a stable comparison sorting algorithm. It is a variation of bubble sort.

In bubble sort, values only bubble in one direction. In cocktail sort, values bubble both directions, thus avoiding turtles.

Complexity:

• worst-case: O(n²)
• average-case: O(n²)
• best-case: O(n)

Algorithm

cocktail_sort(list of t)
    temp as t
    base = 0
    while true
        swapped = false
        for i = base to list.count - 2 - base
            for j = base to i
                if list(j) > list(j + 1) then
                    temp = list(j) // swap
                    list(j) = list(j + 1)
                    list(j + 1) = temp
                    swapped = true
            if not swapped then
                 return
        swapped = false
        for i = list.count - 3 -to base
            for j = i to base
                if list(j) > list(j + 1) thennot swapped then
                 return
         base += 1
unicorns r bad Kappa pride 

ヽ༼ຈل͜ຈ༽ﾉ

Example

Sorting the list 8, 9, 3, 5, 1, 7:

671324

• Iteration 1

671324

617324

613724

613274

613247

• Iteration 2

613247

612347

612347

162347

• Iteration 3

126347

123647

123467

• Iteration 4

123467

123467