17.05Beginner / Intermediate5 topics20 min5 interactive animations

Other educational sorts

These sorts are rarely used in production, but each one isolates a useful idea: sorting in both directions, moving far-apart elements early, insertion done with swaps, diminishing gaps, and minimising writes.

Learning goals

Trace cocktail shaker, comb, gnome, shell and cycle sort
Explain the specific weakness of bubble or insertion sort each one targets
Know their complexity and stability

Prerequisites

Bubble sortInsertion sort

17.05.1

Cocktail shaker

Bubble sort moves large values right quickly but small values left by only one step per pass. These slow small values are called turtles. Cocktail shaker sort alternates a forward pass and a backward pass, so turtles also move quickly.

Try the “Turtle at the end” preset, where 1 sits in the last slot: bubble sort needs all 6 passes (21 comparisons), while cocktail sort needs one round trip plus a final check pass (15 comparisons).

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Cocktail shaker sort

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedMovedSorted

Setup

Bubble sort in both directions: forward passes push large values right, backward passes pull small values left.

Step 1 / 46

Java

1public static void cocktailSort(int[] arr) {
2    int start = 0, end = arr.length - 1;
3    boolean swapped = true;
4    while (swapped) {
5        swapped = false;
6        for (int i = start; i < end; i++) {             // forward pass
7            if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); swapped = true; }
8        }
9        if (!swapped) break;
10        end--;
11        swapped = false;
12        for (int i = end - 1; i >= start; i--) {        // backward pass
13            if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); swapped = true; }
14        }
15        start++;
16    }
17}

Live state

0 comparisons0 swaps

start

end

No condition evaluated on this step

Execution trace (dry run table)Show 46 steps

Step	Line	State	What happens
1	L2	start=0 end=6	Bubble sort in both directions: forward passes push large values right, backward passes pull small values left.
2	L6	start=0 end=6 swapped=false	Forward pass.
3	L7	start=0 end=6 i=0	Out of order: swap.
4	L7	start=0 end=6 i=0	Swapped.
5	L7	start=0 end=6 i=1	In order.
6	L7	start=0 end=6 i=2	Out of order: swap.
7	L7	start=0 end=6 i=2	Swapped.
8	L7	start=0 end=6 i=3	Out of order: swap.
9	L7	start=0 end=6 i=3	Swapped.
10	L7	start=0 end=6 i=4	In order.
11	L7	start=0 end=6 i=5	Out of order: swap.
12	L7	start=0 end=6 i=5	Swapped.
13	L10	start=0 end=5	The largest remaining value is fixed. end = 5.
14	L12	start=0 end=5 swapped=false	Backward pass.
15	L13	start=0 end=5 i=4	Out of order: swap.
16	L13	start=0 end=5 i=4	Swapped.
17	L13	start=0 end=5 i=3	In order.
18	L13	start=0 end=5 i=2	In order.
19	L13	start=0 end=5 i=1	Out of order: swap.
20	L13	start=0 end=5 i=1	Swapped.
21	L13	start=0 end=5 i=0	Out of order: swap.
22	L13	start=0 end=5 i=0	Swapped.
23	L15	start=1 end=5 swapped=true	The smallest remaining value is fixed. start = 1.
24	L6	start=1 end=5 swapped=false	Forward pass.
25	L7	start=1 end=5 i=1	In order.
26	L7	start=1 end=5 i=2	Out of order: swap.
27	L7	start=1 end=5 i=2	Swapped.
28	L7	start=1 end=5 i=3	Out of order: swap.
29	L7	start=1 end=5 i=3	Swapped.
30	L7	start=1 end=5 i=4	In order.
31	L10	start=1 end=4	The largest remaining value is fixed. end = 4.
32	L12	start=1 end=4 swapped=false	Backward pass.
33	L13	start=1 end=4 i=3	In order.
34	L13	start=1 end=4 i=2	In order.
35	L13	start=1 end=4 i=1	Out of order: swap.
36	L13	start=1 end=4 i=1	Swapped.
37	L15	start=2 end=4 swapped=true	The smallest remaining value is fixed. start = 2.
38	L6	start=2 end=4 swapped=false	Forward pass.
39	L7	start=2 end=4 i=2	Out of order: swap.
40	L7	start=2 end=4 i=2	Swapped.
41	L7	start=2 end=4 i=3	In order.
42	L10	start=2 end=3	The largest remaining value is fixed. end = 3.
43	L12	start=2 end=3 swapped=false	Backward pass.
44	L13	start=2 end=3 i=2	In order.
45	L15	start=3 end=3 swapped=false	The smallest remaining value is fixed. start = 3.
46	L17		Sorted with 21 comparisons, 11 swaps.

17.05.2

Comb sort

Comb sort compares elements a gap apart, starting with a gap of about n / 1.3 and shrinking it by 1.3 each pass. Large gaps remove turtles early, and the final gap-1 passes are bubble passes on nearly sorted data.

It is not stable, because long-distance swaps can reorder equal keys.

Best

O(n log n)

Worst

O(n²)

Space

O(1)

Comb sort

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedMovedSorted

Setup

Like bubble sort, but compare elements a gap apart. Large gaps move small values from the end quickly.

Step 1 / 37

Java

1public static void combSort(int[] arr) {
2    int gap = arr.length;
3    boolean sorted = false;
4    while (!sorted) {
5        gap = Math.max(1, (int) (gap / 1.3));        // shrink factor 1.3
6        if (gap == 1) sorted = true;                  // last pass is bubble-like
7        for (int i = 0; i + gap < arr.length; i++) {
8            if (arr[i] > arr[i + gap]) {
9                swap(arr, i, i + gap);
10                sorted = false;
11            }
12        }
13    }
14}

Live state

0 comparisons0 swaps

gap

sorted

false

No condition evaluated on this step

Execution trace (dry run table)Show 37 steps

Step	Line	State	What happens
1	L2	gap=7 sorted=false	Like bubble sort, but compare elements a gap apart. Large gaps move small values from the end quickly.
2	L5	gap=5 sorted=false	gap = 5.
3	L8	gap=5 sorted=false i=0	In order.
4	L8	gap=5 sorted=false i=1	Out of order across the gap: swap.
5	L9	gap=5 sorted=false i=1	Swapped.
6	L5	gap=3 sorted=false	gap = 3.
7	L8	gap=3 sorted=false i=0	Out of order across the gap: swap.
8	L9	gap=3 sorted=false i=0	Swapped.
9	L8	gap=3 sorted=false i=1	Out of order across the gap: swap.
10	L9	gap=3 sorted=false i=1	Swapped.
11	L8	gap=3 sorted=false i=2	In order.
12	L8	gap=3 sorted=false i=3	Out of order across the gap: swap.
13	L9	gap=3 sorted=false i=3	Swapped.
14	L5	gap=2 sorted=false	gap = 2.
15	L8	gap=2 sorted=false i=0	In order.
16	L8	gap=2 sorted=false i=1	In order.
17	L8	gap=2 sorted=false i=2	Out of order across the gap: swap.
18	L9	gap=2 sorted=false i=2	Swapped.
19	L8	gap=2 sorted=false i=3	In order.
20	L8	gap=2 sorted=false i=4	Out of order across the gap: swap.
21	L9	gap=2 sorted=false i=4	Swapped.
22	L5	gap=1 sorted=true	gap = 1. With gap 1 this pass is a bubble pass; if it makes no swaps we are done.
23	L8	gap=1 sorted=true i=0	In order.
24	L8	gap=1 sorted=true i=1	In order.
25	L8	gap=1 sorted=true i=2	In order.
26	L8	gap=1 sorted=true i=3	In order.
27	L8	gap=1 sorted=true i=4	In order.
28	L8	gap=1 sorted=true i=5	Out of order across the gap: swap.
29	L9	gap=1 sorted=false i=5	Swapped.
30	L5	gap=1 sorted=true	gap = 1. With gap 1 this pass is a bubble pass; if it makes no swaps we are done.
31	L8	gap=1 sorted=true i=0	In order.
32	L8	gap=1 sorted=true i=1	In order.
33	L8	gap=1 sorted=true i=2	In order.
34	L8	gap=1 sorted=true i=3	In order.
35	L8	gap=1 sorted=true i=4	In order.
36	L8	gap=1 sorted=true i=5	In order.
37	L14		Sorted with 23 comparisons, 7 swaps.

17.05.3

Gnome sort

A gnome looks at the pot beside it: if the two are in order it steps forward, otherwise it swaps them and steps back. It is insertion sort written as a single loop with swaps.

It is stable and adaptive, with the same O(n²) worst case as insertion sort but more writes.

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Gnome sort

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedMovedSorted

Setup

A gnome walks forward while pots are in order and steps back after each swap.

Step 1 / 60

Java

1public static void gnomeSort(int[] arr) {
2    int i = 0;
3    while (i < arr.length) {
4        if (i == 0 || arr[i - 1] <= arr[i]) {
5            i++;                                // step forward
6        } else {
7            swap(arr, i, i - 1);
8            i--;                                // step back
9        }
10    }
11}

Live state

0 comparisons0 swaps

No condition evaluated on this step

Execution trace (dry run table)Show 60 steps

Step	Line	State	What happens
1	L2	i=0	A gnome walks forward while pots are in order and steps back after each swap.
2	L4	i=0	In order, step forward.
3	L5	i=1	i = 1.
4	L4	i=1	Out of order, swap and step back.
5	L7	i=1	Swapped.
6	L4	i=0	In order, step forward.
7	L5	i=1	i = 1.
8	L4	i=1	In order, step forward.
9	L5	i=2	i = 2.
10	L4	i=2	In order, step forward.
11	L5	i=3	i = 3.
12	L4	i=3	Out of order, swap and step back.
13	L7	i=3	Swapped.
14	L4	i=2	Out of order, swap and step back.
15	L7	i=2	Swapped.
16	L4	i=1	Out of order, swap and step back.
17	L7	i=1	Swapped.
18	L4	i=0	In order, step forward.
19	L5	i=1	i = 1.
20	L4	i=1	In order, step forward.
21	L5	i=2	i = 2.
22	L4	i=2	In order, step forward.
23	L5	i=3	i = 3.
24	L4	i=3	In order, step forward.
25	L5	i=4	i = 4.
26	L4	i=4	Out of order, swap and step back.
27	L7	i=4	Swapped.
28	L4	i=3	Out of order, swap and step back.
29	L7	i=3	Swapped.
30	L4	i=2	Out of order, swap and step back.
31	L7	i=2	Swapped.
32	L4	i=1	In order, step forward.
33	L5	i=2	i = 2.
34	L4	i=2	In order, step forward.
35	L5	i=3	i = 3.
36	L4	i=3	In order, step forward.
37	L5	i=4	i = 4.
38	L4	i=4	In order, step forward.
39	L5	i=5	i = 5.
40	L4	i=5	In order, step forward.
41	L5	i=6	i = 6.
42	L4	i=6	Out of order, swap and step back.
43	L7	i=6	Swapped.
44	L4	i=5	Out of order, swap and step back.
45	L7	i=5	Swapped.
46	L4	i=4	Out of order, swap and step back.
47	L7	i=4	Swapped.
48	L4	i=3	Out of order, swap and step back.
49	L7	i=3	Swapped.
50	L4	i=2	In order, step forward.
51	L5	i=3	i = 3.
52	L4	i=3	In order, step forward.
53	L5	i=4	i = 4.
54	L4	i=4	In order, step forward.
55	L5	i=5	i = 5.
56	L4	i=5	In order, step forward.
57	L5	i=6	i = 6.
58	L4	i=6	In order, step forward.
59	L5	i=7	i = 7.
60	L11		Sorted with 26 comparisons, 11 swaps. Gnome sort is insertion sort done with swaps.

17.05.4

Shell sort intro

Shell sort runs insertion sort on elements gap apart, then shrinks the gap. With gap h, the array becomes h-sorted, meaning every h-th element forms a sorted list. The final gap of 1 is plain insertion sort on nearly sorted data, which is fast.

The gap sequence decides the complexity. Shell's original n/2, n/4, … has an O(n²) worst case. Knuth's (3^k - 1)/2 sequence (1, 4, 13, 40, …) gives O(n^1.5).

Best

O(n log n)

Worst

O(n²) with n/2 gaps

Space

O(1)

Shell sort

Interactive · edit the input

int[] arr · length 7

0123456

Key in handBeing comparedMovedSorted

Setup

Insertion sort on elements gap apart, with the gap halving each round. Far-away elements move early.

Step 1 / 48

Java

1public static void shellSort(int[] arr) {
2    int n = arr.length;
3    for (int gap = n / 2; gap > 0; gap /= 2) {
4        for (int i = gap; i < n; i++) {             // gapped insertion sort
5            int temp = arr[i];
6            int j = i;
7            while (j >= gap && arr[j - gap] > temp) {
8                arr[j] = arr[j - gap];
9                j -= gap;
10            }
11            arr[j] = temp;
12        }
13    }
14}

Live state

0 comparisons0 shifts

No condition evaluated on this step

Execution trace (dry run table)Show 48 steps

Step	Line	State	What happens
1	L2	n=7	Insertion sort on elements gap apart, with the gap halving each round. Far-away elements move early.
2	L3	gap=3	gap = 3: the array is split into 3 interleaved sub-lists.
3	L5	gap=3 i=3 temp=3 j=3	temp = 3. Insert it into its gap-3 sub-list.
4	L7	gap=3 i=3 temp=3 j=3	Shift the larger element gap positions right.
5	L8	gap=3 i=3 temp=3 j=3	arr[3] = arr[0].
6	L7	gap=3 i=3 temp=3 j=0	Stop shifting.
7	L11	gap=3 i=3 temp=3 j=0	arr[0] = 3.
8	L5	gap=3 i=4 temp=9 j=4	temp = 9. Insert it into its gap-3 sub-list.
9	L7	gap=3 i=4 temp=9 j=4	Shift the larger element gap positions right.
10	L8	gap=3 i=4 temp=9 j=4	arr[4] = arr[1].
11	L7	gap=3 i=4 temp=9 j=1	Stop shifting.
12	L11	gap=3 i=4 temp=9 j=1	arr[1] = 9.
13	L5	gap=3 i=5 temp=82 j=5	temp = 82. Insert it into its gap-3 sub-list.
14	L7	gap=3 i=5 temp=82 j=5	Stop shifting.
15	L11	gap=3 i=5 temp=82 j=5	arr[5] = 82.
16	L5	gap=3 i=6 temp=10 j=6	temp = 10. Insert it into its gap-3 sub-list.
17	L7	gap=3 i=6 temp=10 j=6	Shift the larger element gap positions right.
18	L8	gap=3 i=6 temp=10 j=6	arr[6] = arr[3].
19	L7	gap=3 i=6 temp=10 j=3	Stop shifting.
20	L11	gap=3 i=6 temp=10 j=3	arr[3] = 10.
21	L3	gap=1	gap = 1: the array is split into 1 interleaved sub-lists.
22	L5	gap=1 i=1 temp=9 j=1	temp = 9. Insert it into its gap-1 sub-list.
23	L7	gap=1 i=1 temp=9 j=1	Stop shifting.
24	L11	gap=1 i=1 temp=9 j=1	arr[1] = 9.
25	L5	gap=1 i=2 temp=43 j=2	temp = 43. Insert it into its gap-1 sub-list.
26	L7	gap=1 i=2 temp=43 j=2	Stop shifting.
27	L11	gap=1 i=2 temp=43 j=2	arr[2] = 43.
28	L5	gap=1 i=3 temp=10 j=3	temp = 10. Insert it into its gap-1 sub-list.
29	L7	gap=1 i=3 temp=10 j=3	Shift the larger element gap positions right.
30	L8	gap=1 i=3 temp=10 j=3	arr[3] = arr[2].
31	L7	gap=1 i=3 temp=10 j=2	Stop shifting.
32	L11	gap=1 i=3 temp=10 j=2	arr[2] = 10.
33	L5	gap=1 i=4 temp=27 j=4	temp = 27. Insert it into its gap-1 sub-list.
34	L7	gap=1 i=4 temp=27 j=4	Shift the larger element gap positions right.
35	L8	gap=1 i=4 temp=27 j=4	arr[4] = arr[3].
36	L7	gap=1 i=4 temp=27 j=3	Stop shifting.
37	L11	gap=1 i=4 temp=27 j=3	arr[3] = 27.
38	L5	gap=1 i=5 temp=82 j=5	temp = 82. Insert it into its gap-1 sub-list.
39	L7	gap=1 i=5 temp=82 j=5	Stop shifting.
40	L11	gap=1 i=5 temp=82 j=5	arr[5] = 82.
41	L5	gap=1 i=6 temp=38 j=6	temp = 38. Insert it into its gap-1 sub-list.
42	L7	gap=1 i=6 temp=38 j=6	Shift the larger element gap positions right.
43	L8	gap=1 i=6 temp=38 j=6	arr[6] = arr[5].
44	L7	gap=1 i=6 temp=38 j=5	Shift the larger element gap positions right.
45	L8	gap=1 i=6 temp=38 j=5	arr[5] = arr[4].
46	L7	gap=1 i=6 temp=38 j=4	Stop shifting.
47	L11	gap=1 i=6 temp=38 j=4	arr[4] = 38.
48	L14		Sorted with 15 comparisons, 7 shifts. The final gap-1 pass is plain insertion sort on nearly sorted data, which is fast.

17.05.5

Cycle sort intro

Cycle sort counts how many elements are smaller than an item to find its exact final position, writes it there, picks up the displaced value, and repeats until the cycle closes.

Every value is written at most once into its final slot, so the total writes are at most n. This makes it theoretically optimal in writes, which suits memory where writes are costly. It is O(n²) time and not stable.

Best

O(n²)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Cycle sort

Interactive · edit the input

int[] arr · length 7

0123456

CandidateBeing comparedMovedSorted

Setup

Each value is written directly to its final position. Cycle sort minimises memory writes.

Step 1 / 30

Java

1public static int cycleSort(int[] arr) {
2    int writes = 0;
3    for (int start = 0; start < arr.length - 1; start++) {
4        int item = arr[start];
5        int pos = start;
6        for (int i = start + 1; i < arr.length; i++) if (arr[i] < item) pos++;
7        if (pos == start) continue;                 // already in place
8        while (item == arr[pos]) pos++;             // skip duplicates
9        int tmp = arr[pos]; arr[pos] = item; item = tmp;
10        writes++;
11        while (pos != start) {                      // rotate the rest of the cycle
12            pos = start;
13            for (int i = start + 1; i < arr.length; i++) if (arr[i] < item) pos++;
14            while (item == arr[pos]) pos++;
15            tmp = arr[pos]; arr[pos] = item; item = tmp;
16            writes++;
17        }
18    }
19    return writes;
20}

Live state

0 comparisons0 writes

writes

No condition evaluated on this step

Execution trace (dry run table)Show 30 steps

Step	Line	State	What happens
1	L2	writes=0	Each value is written directly to its final position. Cycle sort minimises memory writes.
2	L4	start=0 item=38	Pick up item = 38.
3	L6	start=0 item=38 pos=4	4 values after start are smaller than 38, so 38 belongs at index 4.
4	L9	start=0 item=9 pos=4	Write into arr[4]. Now holding the displaced value 9.
5	L13	start=0 item=9 pos=1	1 value after start is smaller than 9, so 9 belongs at index 1.
6	L15	start=0 item=27 pos=1	Write into arr[1]. Holding 27.
7	L13	start=0 item=27 pos=3	3 values after start are smaller than 27, so 27 belongs at index 3.
8	L15	start=0 item=3 pos=3	Write into arr[3]. Holding 3.
9	L13	start=0 item=3 pos=0	0 values after start are smaller than 3, so 3 belongs at index 0.
10	L15	start=0 item=38 pos=0	The cycle closes back at start.
11	L4	start=1 item=9	Pick up item = 9.
12	L6	start=1 item=9 pos=1	0 values after start are smaller than 9, so 9 belongs at index 1.
13	L7	start=1 item=9 pos=1	9 is already in place.
14	L4	start=2 item=43	Pick up item = 43.
15	L6	start=2 item=43 pos=5	3 values after start are smaller than 43, so 43 belongs at index 5.
16	L9	start=2 item=82 pos=5	Write into arr[5]. Now holding the displaced value 82.
17	L13	start=2 item=82 pos=6	4 values after start are smaller than 82, so 82 belongs at index 6.
18	L15	start=2 item=10 pos=6	Write into arr[6]. Holding 10.
19	L13	start=2 item=10 pos=2	0 values after start are smaller than 10, so 10 belongs at index 2.
20	L15	start=2 item=43 pos=2	The cycle closes back at start.
21	L4	start=3 item=27	Pick up item = 27.
22	L6	start=3 item=27 pos=3	0 values after start are smaller than 27, so 27 belongs at index 3.
23	L7	start=3 item=27 pos=3	27 is already in place.
24	L4	start=4 item=38	Pick up item = 38.
25	L6	start=4 item=38 pos=4	0 values after start are smaller than 38, so 38 belongs at index 4.
26	L7	start=4 item=38 pos=4	38 is already in place.
27	L4	start=5 item=43	Pick up item = 43.
28	L6	start=5 item=43 pos=5	0 values after start are smaller than 43, so 43 belongs at index 5.
29	L7	start=5 item=43 pos=5	43 is already in place.
30	L19		Sorted with 47 comparisons, 7 writes. Writes never exceed n.

Practice ladder

Now try it yourself

Easy

Implement cocktail sort with shrinking start/end
Run gnome sort by hand on [3, 1, 2]

Medium

Shell sort with Knuth's gap sequence
Count writes made by cycle sort vs selection sort

Advanced

Find the minimum swaps to sort a permutation using cycle decomposition
Benchmark comb sort's shrink factor between 1.2 and 1.5

Key takeaways

Cocktail and comb sort fix bubble sort's slow turtles in different ways.
Gnome sort is insertion sort with swaps; shell sort is insertion sort with shrinking gaps.
Cycle sort minimises writes at the cost of O(n²) comparisons.