Published by Dimitris Kougioumtzis · Updated
Use insertion sort on progressively smaller gaps.
Sort subsequences separated by a gap, then shrink the gap until an insertion pass finishes the ordering.
When to use Shell sort
Comparing long-distance movement with local insertion.
Choosing an alternative
Comb sort performs gapped pair exchanges rather than sorting each gapped subsequence.
Worked example: input and state changes
Example input
38, 12, 65, 8, 43, 27, 91, 19
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 38, 12, 65, 8, 43, 27, 91, 19 ], "active": [] }Step 4: Swap across gap 1.
State at this checkpoint
{ "values": [ 8, 38, 43, 12, 65, 19, 91, 27 ], "active": [ 1, 0 ] }Step 7: Swap across gap 1.
State at this checkpoint
{ "values": [ 8, 12, 38, 43, 19, 65, 91, 27 ], "active": [ 5, 4 ] }Step 11: Swap across gap 1.
State at this checkpoint
{ "values": [ 8, 12, 19, 38, 43, 27, 65, 91 ], "active": [ 6, 5 ] }Step 14: Complete: values are in ascending order.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [] }
Expected final state
Complete: values are in ascending order.
Complexity and input bounds
Family: Sorting. Time complexity: O(n²) worst.
Space complexity: O(1) auxiliary space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
2ā24 comma-separated integers between 0 and 99.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Performance depends on the gap sequence; bounds for another sequence need not apply.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 | // Sorts a in place. n is the array length. Return value 0 indicates completion. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n) { for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < n; i++) { let j = i; while (j >= gap && a[j - gap] > a[j]) { let t = a[j]; a[j] = a[j - gap]; a[j - gap] = t; j -= gap; } } } return 0; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- A high-speed sorting procedure
D. L. Shell (1959). Research paper.