Algorithms and Data Structures - Shell Sort

Shell Sort is a generalization of Insertion Sort. It was created by Donald Shell in 1959.

Here an example of the Insertion Sort

Characteristics

• Time complexity:
  • Best: Ω(n log(n)) -> Depends on the gap sequence
  • Average: Θ(n^(3/2)) -> Depends on the gap sequence
  • Worst: O(n^2) -> Depends on the gap sequence
• Space complexity: O(1)
• In-place
• Unstable

Demos:

• Original Implementation with tmp variable
• Original Implementation without tmp variable
• Knuth's Sequence
• Hibbard's Sequence
• Sedgewick's Sequence
• Comparisons all versions

Demonstration

• Algorithm Visualizer

References

• Other Algorithms & Data Structures
• A High-Speed Sorting Procedure - D.L. Shell