🦆 Duck Sorting — View Algorithm Code
← Back to Sort✺ Random Order
The typical, average-case scenario. All algorithms must do real work. Bubble and Insertion Sort take roughly O(n²) steps. 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).
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²).
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.
● 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
● 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