Sortowanie Shella Mariusz: Przypuśćmy że mamy ciągi odstępów zdefiniowane następująco a₀=1 a_n=2a_n−1+1 b₀=1 b_n=3b_n−1+1 Natomiast ciąg c_n jest scaleniem powyższych dwóch ciągów tak jak w przypadku sortowania przez scalanie przy czym podczas scalania elementy powtarzające się bierzemy tylko raz Jaka będzie złożoność czasowa sortowania Shella z podanymi ciągami odstępów ? Załóżmy że mamy daną liczbę całkowitą dodatnią oznaczającą liczbę elementów tablicy Ile jest wyrazów w ciągu Pratta mniejszych lub równych danej liczbie (aby zaallokować dokładnie tyle pamięci na tablicę z wyrazami ciągu Pratta ile potrzeba) Teraz tzw pytanie otwarte Czy sortowanie Shella może osiągnąć złożoność czasową O(nlogn) Jak wyglądałby przykładowy ciąg odstępów który dawałby złożoność czasową O(nlogn)