✺ Random Order
The typical, average-case scenario. All algorithms must do real work. Bubble and Insertion Sort take roughly O(n²) steps. Cocktail Shaker Sort is also O(n²) but typically finishes in fewer rounds than plain Bubble Sort because both ends shrink simultaneously. Comb Sort uses a shrink factor of 1.3 to generate more gap levels than Shell Sort, often finishing in fewer total comparisons than Bubble or Cocktail. Shell Sort often finishes with noticeably fewer steps because its large-gap passes pre-sort the data before the final cheap pass.
A → Z (Ascending – Best Case)
The array is already sorted.
Bubble Sort detects zero swaps in the very first pass and exits immediately: O(n).
Cocktail Shaker Sort likewise exits after the first forward pass finds zero swaps: O(n).
Comb Sort exits after its first gap-1 pass finds zero swaps: O(n) for that final pass, though the gap-reduction passes still run.
Insertion Sort finds every duck already in place with no shifts needed: O(n).
Selection Sort still scans every remaining duck each pass: always O(n²).
Shell Sort likewise finishes very quickly – each gap pass finds nothing out of order.
Z → A (Descending – Worst Case)
The array is in reverse order – the hardest starting point.
Bubble Sort must make all n−1 full passes: O(n²).
Cocktail Shaker Sort is marginally better – its backward passes push small values left quickly, reducing the total number of rounds: still O(n²) but with a smaller constant.
Comb Sort handles reverse order better than plain Bubble or Cocktail: the large initial gaps (6, 4, 3…) move ducks far toward their targets before the gap-1 passes begin.
Insertion Sort shifts every duck the maximum distance: O(n²).
Selection Sort is unchanged – same O(n²) as always.
Shell Sort handles this best: large-gap passes quickly
move ducks close to their targets, so the final gap = 1 pass is very cheap.
⇅ Swap-and-repeat family
● Bubble Sort
- ✓ Compares adjacent pairs only
- ✓ Sorted region grows from the right
- ✓ Each pass “bubbles” the largest remaining duck to the end
- ✓ Early exit if a pass has zero swaps
- Worst case: O(n²) | Best case: O(n)
- A→Z 1 pass (early exit)
- Z→A n−1 passes
● Cocktail Shaker Sort
- ✓ Bubble Sort in both directions each round
- ✓ Sorted region grows from both ends simultaneously
- ✓ Forward pass locks the largest; backward pass locks the smallest
- ✓ Early exit if either pass has zero swaps
- Worst case: O(n²) | Best case: O(n)
- A→Z 1 forward pass (early exit)
- Z→A slightly fewer rounds than Bubble
● Comb Sort
- ✓ Bubble Sort with a shrinking gap (factor 1.3)
- ✓ Gap sequence for 8 ducks: 6 → 4 → 3 → 2 → 1
- ✓ Large gaps move ducks far toward their target cheaply
- ✓ Gap‑1 passes repeat until zero swaps (like Bubble)
- Worst case: O(n²) | Average: better than Bubble
- A→Z gap passes run; gap-1 exits immediately
- Z→A better than Bubble; large gaps help
▲ Pick-and-place family
● Insertion Sort
- ✓ Picks up one duck and slides it left into place
- ✓ Sorted region grows from the left
- ✓ Efficient when data is nearly sorted
- ✓ Shifts, not swaps – fewer writes
- Worst case: O(n²) | Best case: O(n)
- A→Z no shifts at all
- Z→A maximum shifts
● Selection Sort
- ✓ Scans for the minimum each pass
- ✓ Sorted region grows from the left
- ✓ Only one swap per pass (fewest swaps overall)
- ✓ Performance unchanged whether data is sorted or not
- Always O(n²) | O(n) swaps
- Any same step count always
● Shell Sort
- ✓ Generalisation of Insertion Sort using a shrinking gap
- ✓ Gap sequence: n/2, n/4, …, 1 (Shell’s halving)
- ✓ Large gaps move ducks far toward their target quickly
- ✓ Final gap = 1 is Insertion Sort on a nearly-sorted row
- Worst case: O(n²) | Average: O(n·log²n)
- A→Z fastest finish
- Z→A best vs others
Algorithm Code
Scroll up to watch the ducks sort while this panel stays open.