Cocktail Sort is a bidirectional variation of Bubble Sort, where elements are alternately sorted from left to right and right to left. This alternating approach allows smaller elements to move to the front and larger elements to the end in fewer passes than the traditional Bubble Sort. While Cocktail Sort is simple to implement, its time complexity remains **O(n²)** in both average and worst cases, which makes it inefficient for large datasets. This blog post will walk through implementing Cocktail Sort in Python, provide detailed pseudocode, and evaluate its performance on different arrays.

### What is Cocktail Sort?

Cocktail Sort, Shaker Sort or Bidirectional Bubble Sort is a simple comparison-based sorting algorithm. It alternates between left-to-right and right-to-left passes through the array, moving larger elements to the end and smaller elements to the beginning. This bidirectional approach reduces the number of passes compared to traditional Bubble Sort, making it more efficient for arrays that are already partially sorted.

**Time Complexity**:

**Best Case**: O(n) when the array is already sorted.**Average Case**: O(n²), similar to Bubble Sort.**Worst Case**: O(n²) when the array is in reverse order.

### How Cocktail Sort Works

The Cocktail Sort algorithm works as follows:

**Left-to-Right Pass**: Traverse the array from left to right, swapping adjacent elements if they are in the wrong order (i.e., larger element before a smaller one).**Right-to-Left Pass**: After the first pass, traverse the array in the opposite direction, from right to left, again swapping adjacent elements if needed.**Repeat**: Continue alternating between the left-to-right and right-to-left passes until no swaps are required, indicating that the array is sorted.

Below, you can see a visualization of how Cocktail Sort works. Choose the length of your array in the box next to `Array Size (Max 30)`

then click `Generate Random Array`

to generate the numbers, then click `Start Sorting`

.

## Pseudocode for Cocktail Sort

function CocktailSort(arr): n = length(arr) start = 0 end = n - 1 swapped = true while swapped is true: swapped = false # Left to right pass for i from start to end - 1: if arr[i] > arr[i + 1]: swap arr[i] and arr[i + 1] swapped = true if swapped is false: break swapped = false end = end - 1 # Right to left pass for i from end - 1 to start: if arr[i] > arr[i + 1]: swap arr[i] and arr[i + 1] swapped = true start = start + 1

## Python Implementation of Cocktail Sort

def cocktail_sort(arr): n = len(arr) swapped = True start = 0 end = n - 1 while swapped: swapped = False # Traverse the list from left to right for i in range(start, end): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True if not swapped: break swapped = False end -= 1 # Traverse the list from right to left for i in range(end - 1, start - 1, -1): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True start += 1 # Example usage: arr = [5, 3, 8, 4, 2, 7, 1, 10] cocktail_sort(arr) print("Sorted array:", arr)

### Step-by-Step Walkthrough Example

Let’s walk through an example of Cocktail Sort with the array `[5, 3, 8, 4, 2, 7, 1, 10]`

:

#### Step 1: Original array

[5, 3, 8, 4, 2, 7, 1, 10]

#### Step 2: Left to Right pass

- Compare
`5`

and`3`

, swap:`[3, 5, 8, 4, 2, 7, 1, 10]`

- Compare
`5`

and`8`

, no swap. - Compare
`8`

and`4`

, swap:`[3, 5, 4, 8, 2, 7, 1, 10]`

- Compare
`8`

and`2`

, swap:`[3, 5, 4, 2, 8, 7, 1, 10]`

- Compare
`8`

and`7`

, swap:`[3, 5, 4, 2, 7, 8, 1, 10]`

- Compare
`8`

and`1`

, swap:`[3, 5, 4, 2, 7, 1, 8, 10]`

- Compare
`8`

and`10`

, no swap.

After the first pass:

[3, 5, 4, 2, 7, 1, 8, 10]

#### Step 3: Right to Left pass

- Compare
`8`

and`1`

, no swap. - Compare
`7`

and`1`

, swap:`[3, 5, 4, 2, 1, 7, 8, 10]`

- Compare
`4`

and`2`

, swap:`[3, 5, 2, 4, 1, 7, 8, 10]`

- Compare
`5`

and`2`

, swap:`[3, 2, 5, 4, 1, 7, 8, 10]`

- Compare
`3`

and`2`

, swap:`[2, 3, 5, 4, 1, 7, 8, 10]`

After the second pass:

[2, 3, 5, 4, 1, 7, 8, 10]

#### Step 4: Left to Right pass

- Compare
`3`

and`5`

, no swap. - Compare
`5`

and`4`

, swap:`[2, 3, 4, 5, 1, 7, 8, 10]`

- Compare
`5`

and`1`

, swap:`[2, 3, 4, 1, 5, 7, 8, 10]`

After the third pass:

[2, 3, 4, 1, 5, 7, 8, 10]

#### Step 5: Right to Left pass

- Compare
`5`

and`1`

, no swap. - Compare
`4`

and`1`

, swap:`[2, 3, 1, 4, 5, 7, 8, 10]`

- Compare
`3`

and`1`

, swap:`[2, 1, 3, 4, 5, 7, 8, 10]`

After the fourth pass:

[2, 1, 3, 4, 5, 7, 8, 10]

#### Step 6: Left to Right pass

- Compare
`2`

and`1`

, swap:`[1, 2, 3, 4, 5, 7, 8, 10]`

After the fifth pass, no more swaps are needed, and the array is sorted.

Final sorted array:

[1, 2, 3, 4, 5, 7, 8, 10]

### Performance Testing

To test Cocktail Sort’s performance, we’ll compare its behaviour on three types of arrays: **random**, **sorted**, and **reverse sorted**, and we’ll measure the time taken for different array sizes.

import time import random # Cocktail Sort implementation def cocktail_sort(arr): n = len(arr) swapped = True start = 0 end = n - 1 while swapped: swapped = False for i in range(start, end): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True if not swapped: break swapped = False end -= 1 for i in range(end - 1, start - 1, -1): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True start += 1 # Function to run and time the sorting process def test_performance(array_type, size): if array_type == "random": arr = random.sample(range(1, size + 1), size) elif array_type == "sorted": arr = list(range(1, size + 1)) elif array_type == "reverse": arr = list(range(size, 0, -1)) start_time = time.time() cocktail_sort(arr) end_time = time.time() return (end_time - start_time) * 1000 # Time in milliseconds # Array sizes to test sizes = [1000, 5000, 10000] # Test all array types and sizes results = {} for array_type in ["random", "sorted", "reverse"]: results[array_type] = {} for size in sizes: results[array_type][size] = test_performance(array_type, size) # Print the results for array_type, size_results in results.items(): print(f"Performance for {array_type} arrays:") for size, time_taken in size_results.items(): print(f"Array size {size}: {time_taken:.2f} ms")

### Performance Results

Array Type | Size 1000 (ms) | Size 5000 (ms) | Size 10000 (ms) |
---|---|---|---|

Random | 51.95 ms | 1152.25 ms | 4900.54 ms |

Sorted | 0.05 ms | 0.30 ms | 0.57 ms |

Reverse Sorted | 65.87 ms | 1866.85 ms | 7154.78 ms |

**Table1: Performance results for Cocktail Sort on Different Arrays**

### Analysis of Results

**Random Arrays**

- Array size 1000:
**51.95 ms** - Array size 5000:
**1152.25 ms** - Array size 10000:
**4900.54 ms**

For **random arrays**, Cocktail Sort’s performance scales poorly as the array size increases. With smaller arrays (like size 1000), the sort completes fairly quickly, but the time taken increases significantly as the size grows to 5000 and 10000. This is due to Cocktail Sort’s O(n²) time complexity, which causes the number of comparisons and swaps to increase quadratically as the array size grows.

- For size 5000, the performance is
**22 times slower**than for size 1000. - For size 10000, the performance is almost
**4.25 times slower**than for size 5000.

The increasing time for larger arrays is a direct consequence of the algorithm’s quadratic behavior, making Cocktail Sort inefficient for large datasets that aren’t already partially sorted.

**Sorted Arrays**

- Array size 1000:
**0.05 ms** - Array size 5000:
**0.30 ms** - Array size 10000:
**0.57 ms**

For **sorted arrays**, Cocktail Sort performs exceptionally well. Since the array is already in order, Cocktail Sort detects this early and terminates after the first pass, leading to almost constant time performance. The time is minimal for all tested sizes, even for size 10000.

- For size 1000, the sorting completes in
**0.05 ms**, which is almost negligible. - Even for size 10000, it only takes
**0.57 ms**, showing how quickly the algorithm detects the sorted state.

This demonstrates Cocktail Sort’s efficiency in best-case scenarios where the data is already sorted or nearly sorted, significantly outperforming the worst-case scenario.

**Reverse Sorted Arrays**

- Array size 1000:
**65.87 ms** - Array size 5000:
**1866.85 ms** - Array size 10000:
**7154.78 ms**

The **reverse sorted arrays** represent the worst-case scenario for Cocktail Sort. Every element is in the opposite position from its sorted position, meaning the algorithm has to perform the maximum number of comparisons and swaps during both left-to-right and right-to-left passes.

- For size 1000, the algorithm takes
**65.87 ms**, which is already slower than the random array for the same size. - For size 5000, the time jumps to
**1866.85 ms**, which is approximately**28 times slower**than size 1000. - For size 10000, the time increases significantly to
**7154.78 ms**, making it**3.8 times slower**than size 5000.

The drastic increase in time is because each element needs to be moved across the array during the alternating passes, making Cocktail Sort very inefficient when the array is in reverse order. This further illustrates the algorithm’s O(n²) complexity in the worst case, making approximately n²/2 comparisons and swaps.

### Detailed Observations

**Scaling with Array Size:**- In the case of random and reverse arrays, we can observe the quadratic growth in time, confirming the O(n²) complexity of Cocktail Sort. As the array size increases, the time grows drastically, making Cocktail Sort unsuitable for large datasets unless they are nearly sorted.
- The time increase is almost negligible for sorted arrays. The algorithm terminates early when no swaps are required, leading to a best-case performance of O(n), as it only needs one full pass to confirm the array is sorted.

**Worst-case Scenario:**- The reverse sorted array demonstrates the worst-case scenario for Cocktail Sort. In this case, every element is out of place, and the algorithm has to perform the maximum swaps and comparisons in both the forward and backward passes. This leads to excessive time complexity, making the algorithm impractical for reverse-ordered data.

**Best-case Scenario:**- Cocktail Sort performs extremely well when the array is already sorted. It makes one complete pass from left to right, detects no swaps are needed, and terminates early. This highlights the algorithm’s efficiency in nearly sorted datasets, where it can quickly confirm the array is already sorted without unnecessary operations.

**Practical Consideration:**- Due to its simplicity and bidirectional approach, Cocktail Sort can be a reasonable choice for small datasets or nearly sorted arrays. However, for large datasets or datasets that are far from being sorted (like reverse arrays), more efficient algorithms like Quick Sort, Merge Sort, or even Insertion Sort would be preferable.
- The algorithm’s performance is closer to Bubble Sort, and the bidirectional passes provide a slight improvement over unidirectional sorting. However, the O(n²) complexity makes it unsuitable for most real-world applications where performance is a concern.

### Why and How Performance Testing Results Can Vary

The performance of Cocktail Sort can vary drastically based on the initial order of the input array:

**Best-case (sorted arrays)**: The algorithm detects that no swaps are needed after the first pass and terminates early, resulting in an O(n) time complexity.**Worst-case (reverse arrays)**: Every element is out of order, and the algorithm must perform a full pass in both directions for each element, leading to O(n²) complexity.**Average-case (random arrays)**: Cocktail Sort performs reasonably well on small arrays, but its performance degrades rapidly as the array size increases due to its O(n²) complexity.

## Comparing Cocktail Sort to Bubble Sort

Let’s go through the performance differences between Cocktail and Bubble sort for the sorted, reverse, and random arrays of different sizes.

import time import random # Cocktail Sort implementation def cocktail_sort(arr): n = len(arr) swapped = True start = 0 end = n - 1 while swapped: swapped = False # Left to right pass for i in range(start, end): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True if not swapped: break swapped = False end -= 1 # Right to left pass for i in range(end - 1, start - 1, -1): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True start += 1 # Bubble Sort implementation def bubble_sort(arr): n = len(arr) for i in range(n): swapped = False # Traverse the array for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True # If no two elements were swapped, break if not swapped: break # Function to run and time the sorting process def test_sorting_algorithm(sort_func, array_type, size): if array_type == "random": arr = random.sample(range(1, size + 1), size) elif array_type == "sorted": arr = list(range(1, size + 1)) elif array_type == "reverse": arr = list(range(size, 0, -1)) start_time = time.time() sort_func(arr) end_time = time.time() return (end_time - start_time) * 1000 # Time in milliseconds # Array sizes to test sizes = [1000, 5000, 10000] # Test all array types and sizes for Cocktail Sort and Bubble Sort results = {"cocktail_sort": {}, "bubble_sort": {}} for sort_name, sort_func in [("cocktail_sort", cocktail_sort), ("bubble_sort", bubble_sort)]: for array_type in ["random", "sorted", "reverse"]: results[sort_name][array_type] = {} for size in sizes: time_taken = test_sorting_algorithm(sort_func, array_type, size) results[sort_name][array_type][size] = time_taken print(f"{sort_name} on {array_type} array of size {size}: {time_taken:.2f} ms")

### Performance Results: Cocktail Sort vs. Bubble Sort

Array Type | Size | Cocktail Sort (ms) | Bubble Sort (ms) |
---|---|---|---|

Random | 1000 | 52.73 | 46.29 |

Random | 5000 | 1111.63 | 1253.94 |

Random | 10000 | 4852.40 | 5165.25 |

Sorted | 1000 | 0.06 | 0.05 |

Sorted | 5000 | 0.35 | 0.34 |

Sorted | 10000 | 0.67 | 0.59 |

Reverse | 1000 | 69.60 | 52.14 |

Reverse | 5000 | 1928.64 | 1610.82 |

Reverse | 10000 | 7150.77 | 6677.22 |

**Table 2: Performance Comparison of Cocktail Sort and Bubble Sort on Random, Sorted, and Reverse Arrays of Various Sizes**

### Summary and Analysis

**Random Arrays**:

**For size 1000**: Bubble Sort (46.29 ms) is slightly faster than Cocktail Sort (52.73 ms).**For size 5000**: Cocktail Sort (1111.63 ms) outperforms Bubble Sort (1253.94 ms).**For size 10000**: Cocktail Sort (4852.40 ms) performs slightly better than Bubble Sort (5165.25 ms).

**Analysis**: For random arrays, both algorithms have similar performance, but Cocktail Sort tends to perform slightly better for larger arrays. This is likely due to its bidirectional approach, which helps reduce the number of passes in certain cases.

**Sorted Arrays**:

- For all array sizes, both algorithms perform extremely well, with sorting times below 1 ms. The times are nearly identical, with Bubble Sort (0.05 ms) and Cocktail Sort (0.06 ms) for size 1000 showing minimal difference.

**Analysis**: In the best-case scenario (already sorted arrays), both algorithms terminate early after the first pass. The performance difference is negligible, and both algorithms effectively have O(n) complexity in this case.

**Reverse Arrays**:

**For size 1000**: Bubble Sort (52.14 ms) is faster than Cocktail Sort (69.60 ms).**For size 5000**: Bubble Sort (1610.82 ms) outperforms Cocktail Sort (1928.64 ms).**For size 10000**: Bubble Sort (6677.22 ms) is slightly faster than Cocktail Sort (7150.77 ms).

**Analysis**: In the worst-case scenario (reverse sorted arrays), Bubble Sort consistently outperforms Cocktail Sort. This is because Bubble Sort makes fewer unnecessary backward passes compared to Cocktail Sort, where the bidirectional approach results in more comparisons and swaps when the array is in reverse order.

### Key Takeaways:

**Random Arrays**: Both algorithms have similar performance, with Cocktail Sort slightly outperforming Bubble Sort as array sizes grow.**Sorted Arrays**: Both algorithms perform optimally on already sorted arrays, with negligible differences in sorting times.**Reverse Arrays**: Bubble Sort consistently outperforms Cocktail Sort in reverse sorted arrays due to fewer unnecessary backward passes.

In summary, **Cocktail Sort** offers slight improvements over Bubble Sort in some cases, especially for large random arrays. Still, **Bubble Sort** performs better in worst-case scenarios, such as reverse-sorted arrays. For already sorted data, both algorithms perform equally well.

### Applications of Cocktail Sort

Cocktail Sort is rarely used in practice due to its inefficiency compared to more advanced algorithms like Quick Sort or Merge Sort. However, it is useful in educational contexts to demonstrate the concept of bidirectional sorting. It can also be employed in cases where the dataset is small and partially sorted, as it can handle nearly sorted arrays more efficiently than Bubble Sort.

### Conclusion

Cocktail Sort provides an intuitive, straightforward approach to bidirectional sorting. While it improves Bubble Sort for nearly sorted arrays, its O(n²) time complexity makes it unsuitable for large datasets. Through the performance tests, we’ve seen how Cocktail Sort behaves in different scenarios. Algorithms like Quick Sort or Merge Sort are far more efficient for larger or more complex sorting tasks.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Cocktail Sort in:

JavaScript – How To Do Cocktail Sort in JavaScript

C++ – How To Do Cocktail Sort in C+

Rust – How to do Cocktail Sort in Rust

For further reading on sorting algorithms in Python, go to the articles:

- How to do Insertion Sort in Python
- How to do Quick Sort in Python
- How to do Merge Sort in Python
- How to Do Selection Sort in Python
- How to do Counting Sort in Python
- How to Do Radix Sort in Python
- How to Do Bucket Sort in Python
- How to Do Heap Sort in Python
- How to Do Pigeonhole Sort in Python
- How To Do Comb Sort in Python
- How to Do Shell Sort in Python
- How To Do TimSort in Python

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.