sortingtime-complexityasymptotic-complexity

Worst scenario for shell sort: Θ(N^3/2) or O((NlogN)^2)?

I am looking for worst case of Shell sort. According to this, the worst case is O(N^3/2) but here, it is claimed that the worst case is O((N log N)^2)).

I think that worst case should be a a sequence containing largest vales in odd positions. However, here some gap sequences are introduced with Θ(N^3/2) complexity.

I am trying to figure out what is the actual worst case for Shell sort. So far, according to aforementioned paper, the worst case is O((N log N)^2)) not Θ(N^3/2). In addition, here suggested a worst scenario analysis, that apparently, is not Θ(N^3/2).

Here, a time complexity analysis is done on a certain algorithm with O(N^2) as its worst case.

But, I am completely lost. What is the worst case for Shell sort?

Solution

  • It looks like there isn't just one "Shellsort", but a family of sorting functions parameterized by what is called a gap sequence. Shellsort works by h-sorting a list multiple times for decreasing values of h. The sequences of h's used determines how Shellsort performs. Some sequences give O(N^3/2), some give O(N^2), others give O(N log^2 N), etc.

    Odds are each reference you see is using a different gap sequence to derive their asymptotic bounds.

    Edit: consider the worst possible gap sequence (without repeats) n, n-1, n-2, ..., 1. To get the runtime:

    h    sublists sublist size    comparisons
n    n        1 (n)           0
n-1  n-1      1 (n-2), 2 (1)  1
n-2  n-2      1 (n-4), 2 (2)  2
...
n/2  n/2      2 (n/2)         2n
...
n/3  n/3      3 (n/3)         3n
...
n/4  n/4      4 (n/4)         4n
...
n/n           n (1)           n^2

    So the answer is going to be something like n(1+2+...+n) = n^2(n+1)/2, or O(n^3). This is what I'm thinking the maximum possible complexity would be for gap strictly decreasing gap sequences (gap sequences that aren't strictly decreasing are not interesting since those could be arbitrarily bad).