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

Here an example of the Insertion Sort

• 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

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

• Algorithm Visualizer

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