Shell Sort
Category:
Java
Sorting
Time: 25 min
Difficulty: Medium
Random
Nearly sorted
Reversed
Few unique
Stability:
Unstable
Space Complexity:
O(1)
Time Complexity: Best
Ω(n * log n)
, Worst Θ((n * log * n)² / (log * log n)²)
or Θ((n * log n)² / log * log n)
or Θ(n(log * n)²)
, Average O(n * log n)
Implementierung
Coming soon...
Funktionsweise
- Shell's original sequence:
N/2, N/4, …, 1 - Knuth's increments:
1, 4, 13, …, (3k – 1) / 2 - Sedgewick's increments:
1, 8, 23, 77, 281, 1073, 4193, 16577…4j+1+ 3·2j+ 1 - Hibbard's increments:
1, 3, 7, 15, 31, 63, 127, 255, 511, … - Papernov & Stasevich increment:
1, 3, 5, 9, 17, 33, 65, … - Pratt:
1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81, …