**Introduction**

Cocktail Sort, also known as **Bidirectional Bubble Sort** or **Shaker Sort**, is a variation of Bubble Sort that sorts the array in both directions on each pass through the list. By alternating the sorting direction, Cocktail Sort eliminates turtles (small elements stuck at the end) more quickly, improving the efficiency of Bubble Sort in certain cases.

In this post, we will go over how to implement Cocktail Sort in JavaScript, walk through an example, and discuss the pros, cons, and performance considerations of using this algorithm.

## What is Cocktail Sort?

Cocktail Sort is an extension of Bubble Sort that goes through the array from both forward and backwards directions in each pass. This helps reduce the number of comparisons for cases where large elements are at the start, and small elements are at the end of the array.

**Forward pass**: Like Bubble Sort, it compares adjacent elements and moves the larger one to the end.**Backward pass**: It then compares elements from the back of the array to the start, moving smaller elements to the front.

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**

Here’s the pseudocode for Cocktail Sort:

procedure cocktailSort(A : array of items) repeat swapped = false // Forward pass (left to right) for i = 0 to n-2 do if A[i] > A[i+1] then swap(A[i], A[i+1]) swapped = true // If no elements were swapped, the array is sorted if not swapped then break swapped = false // Backward pass (right to left) for i = n-2 downto 0 do if A[i] > A[i+1] then swap(A[i], A[i+1]) swapped = true until swapped = false

**Time and Space Complexities**

**Time Complexity**:- Worst-case: O(n²) — similar to Bubble Sort, as each element might be compared.
- Best-case: O(n) — if the array is already sorted.

**Space Complexity**:- O(1) — Cocktail Sort operates in place and doesn’t require extra memory.

**JavaScript Implementation**

Now, let’s implement **Cocktail Sort** in JavaScript:

function cocktailSort(arr) { let swapped = true; let start = 0; let end = arr.length; while (swapped) { swapped = false; // Forward pass for (let i = start; i < end - 1; i++) { if (arr[i] > arr[i + 1]) { [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // Swap elements swapped = true; } } // If no elements were swapped, the array is sorted if (!swapped) { break; } // Otherwise, reset the swapped flag for the backward pass swapped = false; // Decrement the end point, as the last element is already sorted end--; // Backward pass for (let i = end - 1; i > start; i--) { if (arr[i - 1] > arr[i]) { [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]]; // Swap elements swapped = true; } } // Increment the starting point, as the first element is already sorted start++; } return arr; } // Example usage: const array = [5, 3, 8, 4, 2, 6, 1, 9]; console.log("Original Array:", array); console.log("Sorted Array:", cocktailSort(array));

**Output:**

Original Array: [ 5, 3, 8, 4, 2, 6, 1, 9 ] Sorted Array: [ 1, 2, 3, 4, 5, 6, 8, 9 ]

**Step-by-Step Explanation of Cocktail Sort**

Let’s break down how Cocktail Sort works for the array `[5, 3, 8, 4, 2, 6, 1, 9]`

:

**Initial Array**:`[5, 3, 8, 4, 2, 6, 1, 9]`

**First Forward Pass**(Left to Right):**Compare 5 and 3**→ Swap →`[3, 5, 8, 4, 2, 6, 1, 9]`

**Compare 5 and 8**→ No swap**Compare 8 and 4**→ Swap →`[3, 5, 4, 8, 2, 6, 1, 9]`

**Compare 8 and 2**→ Swap →`[3, 5, 4, 2, 8, 6, 1, 9]`

**Compare 8 and 6**→ Swap →`[3, 5, 4, 2, 6, 8, 1, 9]`

**Compare 8 and 1**→ Swap →`[3, 5, 4, 2, 6, 1, 8, 9]`

**Compare 8 and 9**→ No swap**End of first forward pass**:`[3, 5, 4, 2, 6, 1, 8, 9]`

**First Backward Pass**(Right to Left):**Compare 8 and 9**→ No swap**Compare 1 and 6**→ Swap →`[3, 5, 4, 2, 1, 6, 8, 9]`

**Compare 1 and 2**→ Swap →`[3, 5, 4, 1, 2, 6, 8, 9]`

**Compare 1 and 4**→ Swap →`[3, 5, 1, 4, 2, 6, 8, 9]`

**Compare 1 and 5**→ Swap →`[3, 1, 5, 4, 2, 6, 8, 9]`

**Compare 1 and 3**→ Swap →`[1, 3, 5, 4, 2, 6, 8, 9]`

**End of first backward pass**:`[1, 3, 5, 4, 2, 6, 8, 9]`

**Second Forward Pass**:**Compare 3 and 5**→ No swap**Compare 5 and 4**→ Swap →`[1, 3, 4, 5, 2, 6, 8, 9]`

**Compare 5 and 2**→ Swap →`[1, 3, 4, 2, 5, 6, 8, 9]`

**Compare 5 and 6**→ No swap**End of second forward pass**:`[1, 3, 4, 2, 5, 6, 8, 9]`

**Second Backward Pass**:**Compare 5 and 6**→ No swap**Compare 2 and 4**→ Swap →`[1, 3, 2, 4, 5, 6, 8, 9]`

**Compare 2 and 3**→ Swap →`[1, 2, 3, 4, 5, 6, 8, 9]`

**End of second backward pass**:`[1, 2, 3, 4, 5, 6, 8, 9]`

**Third Forward Pass**:**Compare 1 and 2**→ No swap**Compare 2 and 3**→ No swap**Compare 3 and 4**→ No swap**End of third forward pass**:`[1, 2, 3, 4, 5, 6, 8, 9]`

**Third Backward Pass**:**Compare 3 and 4**→ No swap**Compare 2 and 3**→ No swap**Compare 1 and 2**→ No swap**End of third backward pass**:`[1, 2, 3, 4, 5, 6, 8, 9]`

The array is fully sorted, so the algorithm terminates.

**Summary of Swaps**:

**First Forward Pass**: 5 with 3, 8 with 4, 8 with 2, 8 with 6, 8 with 1.**First Backward Pass**: 6 with 1, 2 with 1, 4 with 1, 5 with 1, 3 with 1.**Second Forward Pass**: 5 with 4, 5 with 2.**Second Backward Pass**: 4 with 2, 3 with 2.

This detailed breakdown helps clarify how Cocktail Sort compares and swaps elements in both directions, ensuring that the array is sorted more efficiently than traditional Bubble Sort. To see how Cocktail Sort performs, visit our Sorting Algorithm Visualizer.

**Pros and Cons of Cocktail Sort**

**Pros**:

**Efficient for small datasets**: Cocktail Sort works well for small arrays, similar to Bubble Sort but slightly optimized.**Eliminates turtles faster**: The bidirectional nature helps eliminate small values at the end of the array quicker.**Simple to implement**: The algorithm is easy to understand and implement.

**Cons**:

**Inefficient for large datasets**: Like Bubble Sort, Cocktail Sort is a quadratic time algorithm, making it unsuitable for large datasets.**Not widely used in practice**: Due to its O(n²) time complexity, more advanced algorithms like Quick Sort or Merge Sort are preferred for large datasets.

**When to Use Cocktail Sort**

Cocktail Sort is best used when:

- You’re working with small datasets that don’t require a highly efficient sorting algorithm.
- You need a simple sorting algorithm that’s easy to understand and implement.
- You want a slight improvement over Bubble Sort, especially when dealing with arrays with small and large elements scattered throughout.

**Conclusion**

Cocktail Sort improves the basic Bubble Sort by sorting in both directions during each pass. While it’s easy to implement and great for small datasets, its quadratic time complexity makes it unsuitable for large data sets. However, understanding Cocktail Sort helps build a solid foundation for more complex sorting algorithms like **Quick Sort** or **Merge Sort**.

Congratulations on reading to the end of the tutorial!

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

In Python – How to do Cocktail Sort in Python

In Rust – How to do Cocktail Sort in Rust

Have fun and happy researching!

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.