Talk:Shellsort

Copyright violation?

This sounds like it might have been taken straight from a copyrighted textbook. Anyone know the source for sure? Wesley

I found a german version which seems to be a word by word translation. Even the examples are the same. Since the german version is longer, it seems that the english text in wikipedia is taken from there. The URL is http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm

80.145.80.78 20:36, 29 Nov 2003 (UTC) (de:Benutzer:Hubi)

Yes, it seems that page has an English version whence much of this article was copied. But it's gone so long without detection that we've made significant changes. I don't know how we can possibly separate the violating from the nonviolating material at this juncture. We may just have to rewrite the article. Deco 18:10, 15 December 2005 (UTC)

---

Is shell sort different from comb sort?

They are similar but different. Comb sort is to bubbls sort what shell sort is to insertion sort. Bubba73 16:16, August 31, 2005 (UTC)

According to NIST, the difference is that comb sort applies only one pass through the elements at each iteration whereas shell sort completely sorts at each iteration.

---

Has anyone actually *used* shell sort at all recently? Quicksort is much faster in practice, and just as simple to implement, merge sort give you guaranteed n log n performance and only requires sequential access, heapsort is also guaranteed n log n, in-place, with pretty much no overhead whatsoever, and there are a variety of specialised sorting algorithms - for instance, for strings, which have much lower constant factors. Anybody? --Robert Merkel 14:14 May 14, 2003 (UTC)

I actually use Shell sort regularly. Quicksort isn't that much faster than a good shell sort until you get into millions of items. Bubba73 16:16, August 31, 2005 (UTC)

Shell sort is a very powerful algorithm, especially when used in combination with Insertion sort.

---

The sample claims to be in Java, and yet is in C.

No, it uses Java's array syntax. All it's missing is the method access qualifier. Deco 18:12, 15 December 2005 (UTC)

Stover

I didn't know about the work of Stover until a couple of days ago, when I saw it in the article. I did some tests, and it is pretty good. First, however, the Sedgewick sequence he gives in figure 3 is not as good as the Sedgewick sequence in (11) of Knuth, vol 3, 2nd ed, 5.2.1 (which is about 5% faster than the one Stover uses). Nevertheless, Stover's #7 sometimes beats the better Seqgewick sequence, but usually not. Bubba73 16:16, August 31, 2005 (UTC)

Nitrogen peroxyde ?

O(N2) means something else in the context of calculation. Please write it plain. Thanks. --DLL 12:36, 26 January 2006 (UTC)

--> But this is not in the context of calculation, nor chemestry! It is computer science context. It is "Big O Notation" used for complexity of algorithms as most introdutory computer science books will say. — Preceding unsigned comment added by 187.104.42.2 (talk) 11:41, 6 February 2012 (UTC)

Shell or shell ?

For many years I tried to visualize the shells, much as there are moving bubbles in bubble sort. Then I figured out that it was named after its inventor, and it was not an analogy.

Would it be worth capitalizing shell where it appears?

Not all names remain capitalized in compound words, but it seems like a lot of people who write about it do capitalize it. Perhaps we should. Deco 00:21, 3 February 2006 (UTC)

Algorithm question

First of all i think that instead of: for (j = i - gap; j >= 0 && a[j] > value; --j) there should be for (j = i - gap; j >= 0 && a[j] > value; j-=gap)

The code still yields the correct result because in the final step gap=1 and the alg does an insert sort.... But in terms of complexity it won't act well

Secondly i think the algorithm should also be explained in words, most of the time this helps a lot... A similar explanation like the one in the first link of the external links section would be great. I will insert it if you guys don't mind.

I agree with your second point. However, your first point is incorrect; if we were to move j by gap, we would only sort one column of the matrix containing the list rearranged into gap columns, so the sort would not be effective. This is crucial. Deco 00:34, 19 June 2006 (UTC)

Contradiction regarding running time?

At the top of the article, it says "estimates range from O(n ^ 1.25) to O(n ^ 1.5)" - that is, it is believed to be impossible to go below n^1.25. Later it says - "Depending on the choice of gap sequence, Shellsort has a worst-case running time of ... O(n log^2 n)" - which, as far as I understand, means that a sequence is known for which it is n (ln n)^2. Does it mean something else? This is either a contradiction, or a very unclear wording which should be rewritten. Any ideas? -- Meni Rosenfeld (talk) 18:34, 18 June 2006 (UTC)

The person who wrote the 1.25 was probably unfamiliar with the sequence permitting O(nlog²n) shellsort. I've updated it. Deco 00:24, 19 June 2006 (UTC)

Now that's more like it :). Thanks. -- Meni Rosenfeld (talk) 15:00, 19 June 2006 (UTC)

Speaking of which, it provides formulas for the O(n ^ 1.25) and O(n ^ 1.5) sequences, but none for the O(nlog^2(n)) sequence. Why isn't that there? 66.32.36.227 17:46, 7 July 2007 (UTC)

The discussion on running time still doesn't look sane to me. First it is stated that "The existence of an O(n log n) worst-case implementation of Shell sort was precluded..." Then the article says "[with the sequence] 1, 4, 10, 23, 57, 132, 301, 701, 1750 [...] "Shell sort runs faster than an insertion sort or a heap sort". But heapsort is O(n log n), right? Then Shell sort cannot be faster? Do they mean for small enough n? In that case, how small? 188.126.207.212 (talk) 12:37, 11 August 2010 (UTC)

I noticed the same contradiction and removed the "heap sort". If shells sort exceeds Θ(n log n) as is stated in the article, it can't be faster than heap sort for all input sizes. The comment I used is incomplete because I accidentally hit enter and somebody thought it a good idea to make the browser save the page in this case. Aragorn2 (talk) 10:43, 20 September 2010 (UTC)

Need discussion of gap insertion sort and sequence details

I've unlinked gap insertion sort in the article because this algorithm has virtually no use outside of shellsort, and is therefore most appropriate to discuss in this article (correct me if I'm wrong). We need to add discussion of gap insertion sort and of the specific sequences that produce certain asymptotic runtimes. I think it would be helpful to use the matrix characterization, where the list is rewritten as a table of k columns, where k is the gap, and the columns are sorted. Even the summary of this algorithm on the sorting algorithm page is already more complete than this article - maybe we should steal that. Deco 15:06, 19 June 2006 (UTC)

big O/theta consistency

All instances of big O notation are written like O(x), however, in the second line Ω(n2) appears. Is this on purpose? If not, which version should be used?

Dummies102 02:38, 10 February 2007 (UTC)

Ω(n²) simply means that the algorithm has an asymptotic lower bound of n². Big O is roughly the asymptotic upper bound. Best123 00:55, 28 February 2007 (UTC)

Dividing by 2.2

There is a citation needed for the following quote on the page:

For some unexplained reason, when the increment is divided by 2.2 as opposed to being continuously halved, this algorithm works about 25 to 30 per cent faster on large inputs.

While I cannot offer an actual citation, I have tested this sequence and it proves to be very effective. Here is the output from sorting 1000 random elements using the shell sorter on Sedgewick's analysis page linked to in the External Links section:

 19054 comparisons and 19054 exchanges for 1 2 3 4 6 9 8 12 18 27 16.
 11182 comparisons and 11182 exchanges for 1 8 23 77 281 1073 4193.  <Usually considered to be one of the best>
 7412 comparisons and 7412 exchanges for 1 3 7 21 48 112 336 861 1968.
 6668 comparisons and 6668 exchanges for 1 2 4 9 20 44 97 213.  <Divide by 2.2>
 5258 comparisons and 5258 exchanges for 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210.  <Triangular numbers>

Aaron Rotenberg 17:27, 12 March 2007 (UTC)

These numbers are wrong. Are you really claiming that the number of exchanges is identical number of comparisons for random numbers? That means every time a comparison occurs, it is exchanged. Stephen Howe 11:43, 11 May 2007 (UTC)

Indeed. It is well-known that 2.2 performs very well. I haven't seen any papers on it either (perhaps because nobody knows why).

I have been using that page from Princeton. One criticism I can give is that the number of comparisons shown in the output may be bugged, because in reality the number of comparisons will always be greater than or equal to the number of swaps. This is evident when you try to Shellsort more than 100,000 numbers using Pratt's increments. Pratt's increments give the least number of swaps among the roster of increment sequences yet take a longer time to finish (especially if you use ALL possible increments.) Hibbard's increments finish faster even though the sorting algorithm will say that it performed more swaps than when using Pratt's. Try comparing the performance with array sizes of 1,000,000 and up, and you will see what I mean ^_^ (Also, make sure that you're using all the increments corresponding to your array size, otherwise you might not get a favorable result.)

I made variations of Hibbard's increments {1,3,7,15,31...} and Knuth's increments {1,4,13,40,121...} by replacing 2 or 3 with numbers in between, and my empirical results show that the most efficient divisor is approximately between 2.2 and 2.212, for some odd reason that still baffles me now. Most articles about Shellsort talk of the same number, although no one has come up with an answer as to why 2.2 seems to work better than the rest. Best123 05:58, 7 April 2007 (UTC)

I can offer an explanation. The 2.2 factor comes from the "Handbook of Algorithms and Data Structures" by Gonnet and Baeza-Yates. This is an incredible book on algorithms and data structures in its time, out of print, which I have a copy. Worth getting second-hand. Gonnet and Baeza-Yates say that if you decrease the gap by a constant factor ending on 1, the constant factor that appears to work best (empirically determined) for Shell Sort is 0.4545... which is 5/11. The reciprocal is, of course, 2.2. A online link to some of the books algorithms is here

www.dcc.uchile.cl/~rbaeza/handbook/hbook.html

Have a look at the index for an idea of the book. And if you look here

www.dcc.uchile.cl/~rbaeza/handbook/algs/4/414.sort.c.html

you can see the 5/11th factor

The theory behind this, is given N elements, a suitable sequence of gaps is N * α, N * α * α, N * α * α * α, ..., 1 - where α is between 0 and 1. Now If α is close to 1, the gap sequence is too long, each gap does few exchanges. If α is close to 0, the gap sequence is too short, each gap does more exchanges than it should So α being 0.4545... was determined empirically as minimising the number of comparisons/exchanges depending on your criteria. Stephen Howe 22:47, 9 May 2007 (UTC)

I don't have an account, and I don't know if I'm doing this right, either. I don't have much experience with programming (I've only taken three courses at my local high school), but I think I understand part of why this is. Integer rounding, in Java at least, always rounds down (try storing Math.random() as an integer--you always get zero). Maybe offsetting what you're dividing it by can upset the balance a little? --Patrick C.

incrmnt = 3

Why on earth does the C/C++ implementation have a hard-coded starting increment of 3! That certainly isn't right! It should be "incrmnt = size/2", otherwise it's not much of a 'sequence; is it (3, 1)! —The preceding unsigned comment was added by 203.109.182.198 (talk) 05:28, 18 March 2007 (UTC).

This may have fixed the problem, but it is not exactly an optimal solution. Quoted from higher up on the page: "Shellsort has a proven worst-case running time of O(n²) (using Shell's increments that start with 1/2 the array size and divide by 2 each time)." In other words, the C++ code uses the worst possible gap sequence. Aaron Rotenberg 03:39, 21 March 2007 (UTC)

for(incrmnt = 1 ; incrmnt<size;incrmnt=incrmnt*3+1);

Can you explain this line code in a better way?

(A comment deleted by its author. JDAWiseman (talk) 21:10, 3 April 2019 (UTC))

Missing Citation

The run time of O(nlog²n) in the list of worst cases isn't cited with a source. Flamesplash 00:17, 16 August 2007 (UTC)

Is the Python Example Correct?

I am seeing two yield statements, where the second one wont be reached at all. It also uses numpy module, which is unnecessary. got to figure out a better one. Phoe6 10:27, 27 August 2007 (UTC)

I see nothing wrong with the generator function. The second yield statement will be reached because when the generator resumes, it will continue from the point at which it yielded.

The only point I question is whether the Python implementation should be in the article at all. Its inclusion suggests incorrectly that it is a good routine to use; in fact, any pure Python sort implementation will be an order of magnitude slower than the built-in, stable list.sort method, which is implemented in C. Peristarkawan 22:26, 3 October 2007 (UTC)

Algorithm

Does someone want to write a "pure" (not language-specific) algorithm for this? Nnkx00 23:55, 29 October 2007 (UTC)

How about

for g in gapsequence
    for i from 1 to g
        InsertionSort A[i to n by g].

Here "a to b by c" denotes the sequence a, a+c, a+2c, ..., stopping no later than b, with c defaulting to 1 when omitted. (In MATLAB, a:c:b.) "From" is merely a synonym of "in". A[i to n by g] denotes the array A[i], A[i+g], ... stopping no later than the end of A, again as in MATLAB (but with array indexing denoted by the more conventional square brackets rather than MATLAB's round brackets so as not to look like a function call). That InsertionSort is called g times for each g in gapsequence should be pretty clear with this phrasing. Vaughan Pratt (talk) 23:55, 21 January 2015 (UTC)

Best known sequence

I changed the line "The best known sequence is 1, 4, 10, 23, 57, 132, 301, 701, 1750." to "The best known sequence according to research by Marcin Ciura is 1, 4, 10, 23, 57, 132, 301, 701, 1750." because proof of it being optimal is not shown and empirical tests also show it is not optimal, other sequences perform better. Also added another intriguing sequence which performs well. Neverwinterx

Interesting... If empirical tests show that other sequences are better, can you quote one? According to the graphs, Ciura (2001) has the best sequence. 132.244.72.4 (talk) 16:41, 23 November 2012 (UTC)

I also notice that just above the graph, Ciura's sequence ends at 701 and there is no reference to 1750. Why? 132.244.72.4 (talk) 11:43, 26 November 2012 (UTC)

Because 1750 is apocryphal. MCiura (talk) 15:14, 26 November 2012 (UTC)

I can find 1750 in OEIS sequence. http://oeis.org/A102549 83.28.255.254 (talk) 19:59, 28 October 2015 (UTC)

I don't see how "best known sequence" implies that optimality is proven. In fact, using the adjective "known" implies otherwise. "This is the best sequence that we know of - there may be better ones." — Preceding unsigned comment added by 125.239.159.60 (talk) 22:26, 2 April 2018 (UTC)

generalization of insertion sort or bubble sort?

The article states that Shell sort is a generalization of insertion sort. However, according to one source (the O'Reilly book "Mastering Algorithms with Perl"), it's a generalization of bubble sort (or an "advanced cousin" of it, to use that author's words). Which is it? My analysis of the pseudocode in the article seems to verify the latter, but I may be missing something. --Paul (talk) 16:44, 8 June 2009 (UTC)

The short answer is that it can probably be done either way, but it's a lot easier to conceptualise it as a generalization of insertion sort. NIST, in particular, says "On each pass i sets of n/i items are sorted, typically with insertion sort." This could probably be explained somewhat better, or at least more consistently, but there is a risk of introducing confusion if we're not careful. Dcoetzee 18:16, 8 June 2009 (UTC)

The essence of Shell sort is sorting the k-chains (arrays with elements spaced k apart) for progressively smaller k down to and including k = 1. Shell originally used insertion sort but bubble sort would also work. Both insertion sort and bubble sort examine the same number of pairs and make the same number of swaps, just not in the same order, so the running time will be the same. The n log²n Shell sort in my thesis is completely neutral on insertion sort vs. bubble sort because it sorts k-chains simply by scanning the array once for pairs of elements k apart and exchanging them if out of order, with no inner loop to keep moving moved elements along. The reason people specified insertion sort in the 1970s is because that's what Shell specified. Also Knuth in his book on sorting (AOCP 3) limits himself to insertion sort as the only exchange sort in the beginning, and then 25 pages later considers other exchange sorts including bubble sort, mentioning that "the classification ... is not always clear-cut" (but my edition is the 1973 one where he didn't seem to be drawing a clear distinction between insertion methods and exchange methods---in particular he doesn't list insertion sort per se among the exchange sorts which is odd). --Vaughan Pratt (talk) 20:07, 28 March 2011 (UTC)

O(n log n) = O(n log2 n)

Why does this article say that this algorithm is worse than comparison sorts? O(n log n) = O(n log2 n) because log2 of a number is just a constant multiplied by the log in any other base of a number. Constants are factored out in big-O notation. —Preceding unsigned comment added by 97.125.127.247 (talk) 19:05, 17 August 2010 (UTC)

Retracted - saw that it's O(n (log n)^2). —Preceding unsigned comment added by 97.125.127.247 (talk) 19:16, 17 August 2010 (UTC)

Contradiction

In the Analysis section, it is written: "O(N3/2), a bound that cannot be improved."

This is followed immediately by: "A minor change given in V. Pratt's book improved the bound to O(n log2 n)."

The latter clearly contradicts the former; can this be revised? Perhaps the writer meant that the Pratt originally stated (in error) that the bound could not be improved, then retracted the statement when he found a lower bound? Even this interpretation seems unlikely, as it is neither common for a mathematician nor a computer scientist to declare a strict upper bound on algorithmic complexity without a corresponding proof. --204.210.244.48 (talk) 18:38, 14 April 2011 (UTC)

Addendum: After looking this up in other sources I see that this is not referring to the analysis of the bound, but rather, the actual bound itself which changes depending on what increment sequence is used. This should be clarified, because it sounds like the discussion is on possible bounds for the algorithm in general. The O(N3/2) bound may be "precise" for one particular increment sequence (the sequence x' = 3x+1 has this exact bound, for example), but there are increment sequences with better bounds (including the (O nlg^2n) example), and there is no proof of a strict upper bound for this algorithm, other than O(nlgn) which is a strict upper bound for all comparison-based sorting...but no increment choice so far has been proven to reach that level of efficiency. --204.210.244.48 (talk) 18:48, 14 April 2011 (UTC) Don't you mean that O(nlgn) is a strict LOWER bound for all comparison-based sorting? (132.244.72.6 (talk) 14:51, 13 November 2012 (UTC))

In this context chapter 2.2 of my thesis (ref. [9] in the article) shows that there exist broad classes of gap sequences such that for every n there exists an array of that size on which Shellsort takes time Ω(n^3/2) (i.e. time at least proportional to n^3/2 for some constant of proportionality independent of n).

Each such class is determined by an arbitrary choice of reals r,s > 1 and integers a,b ≥ 0. For each such choice there exist nonnegative reals t,u,c, with rt < u, and a class G(r,s,a,b) of gap sequences defined by conditions (i) and (ii) below, such that for all n, Shellsort using any member of that class will require at least cn^3/2 swaps on some array of size n.

(i) The gap sequence must contain a gap p such that p/sqrt(n) lies in the interval [t,u] and every earlier (larger) gap in the gap sequence must lie in some integer multiple m*I of the interval I = [p-a, p+b];

(ii) the gap q immediately following p must lie outside (hence below) I and in the interval [(p-b)/s - a, (p+a)/r + b].

Hibbard's sequence lies in the class G(2,2,0,1), while the sequence floor((3^k - 1)/2) is in G(3,3,0,1). Vaughan Pratt (talk) 09:20, 22 January 2015 (UTC)

RFC: a new version of the article

At User:MCiura/Shellsort, I have put a translation of the Polish article by myself, which is a GA on pl.wikipedia. After it is reviewed, I would like to move it to the main namespace. IMHO, the current explanations are too wordy but if you find something from the present version that you'd like to save, feel free to modify the new page. I will also be grateful for corrections of my English style and comments of any kind. One evident thing: folIowing all the references, I have used the name Shellsort, not Shell sort. Thanks, MCiura (talk) 17:46, 6 August 2011 (UTC)

I've worked on the English of the proposed new article in response to your request on the Guild of Copy Editors Requests page, and I've left some comments on your talk page. In general, I feel that the present lead section is better and that the History section is desirable to keep. (I am not qualified to comment on the technical aspects of the two versions.) --Stfg (talk) 15:03, 5 September 2011 (UTC)

Animation

Anyone knows of a free gif animation to upload? --Solde9 (talk) 15:15, 11 August 2011 (UTC)

Requested move

The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the move request was: article moved. fish&karate 13:39, 26 October 2011 (UTC)

---

Shell sort → Shellsort – 01:01, 8 October 2011 (UTC) As per WP:TITLE, "Article titles are based on what reliable English-language sources refer to the article's subject by.". See the references at User:MCiura/Shellsort: 11 printed papers that spell it Shellsort vs one web page that spells it Shell sort. MCiura (talk)

• Comment Google Scholar "shell-sort" or "shell sort" (1000ghits) "shellsort" (800ghits) -- looks pretty equal to me. 70.24.247.61 (talk) 07:30, 8 October 2011 (UTC)
• Comment Primary sources in Google Scholar: allintitle: "shell-sort" - 13 hits, allintitle: "shellsort" - 62 hits. MCiura (talk) 08:49, 8 October 2011 (UTC)
• Move Follow usage of reliable sources as cited in the article. —Ruud 11:42, 10 October 2011 (UTC)
• Oppose Support move. I don't get the sense that there's overwhelming support for shellsort written solid. Sedgewick uses the solid name, but Knuth used Shell's method. Corman/Leiserson/Rivest/Stein use Shell's sort. I'd give K and CLRS a lot of weight; Sedgewick not so much. Procedures would use the solid name, and that has probably polluted the perception and the hit count. Quicksort is written solid (it's almost Quicksort™), but bubble sort is divided. I don't see a compelling reason to use the solid name. Leave it alone. 64.9.237.127 (talk) 01:36, 11 October 2011 (UTC)
  • I checked Knuth and while he starts the section with "Shell's method" he then consistently names it "shellsort", not "shell sort", throughout the section as well as in the index. Pretty much all of the references used in this article use "shellsort" as well. —Ruud 15:14, 22 October 2011 (UTC)

Ruud should have opened a new RM; this one was closed. Ruud's comment was made by MCiura below.

I switched because Knuth uses "shellsort" with lowercase "s". See

Janson, Svante; Knuth, Donald (January 1997), "Shellsort with three increments", Random Structures and Algorithms, 10 (1–2): 125–142, doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X CiteSeerX 10.1.1.54.9911

Glrx (talk) 01:41, 24 October 2011 (UTC)

Still, I'd be happier with a capitalized "Shell sort"; we don't call the Berlekamp–Massey algorithm the "berlekamp–massey algorithm" or the Risch algorithm the "risch algorithm". Sadly, "shellsort" appears to be an acceptable WP:COMMONNAME. - Glrx (talk) 21:41, 24 October 2011 (UTC)

• Comment Knuth's chapter is called "Shell's method" but inside it he calls the algorithm shellsort (with lowercase s). MCiura (talk) 05:02, 11 October 2011 (UTC)
• Comment FWIW, Cormen et al. mention Shell['s ]sort only once, in passing. MCiura (talk) 10:26, 11 October 2011 (UTC)
• Oppose. Agree with 64.9.237.127 who has analysed the pros and cons very well IMO. Andrewa (talk) 23:49, 16 October 2011 (UTC)
• Support. I also pulled out my old Knuth Volume 3, which I regard as definitive, and confirmed that he referred to it as either Shell's method or shellshort but never as "Shell sort." Msnicki (talk) 21:29, 23 October 2011 (UTC)

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

GA Review

This review is transcluded from Talk:Shellsort/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Vaughan Pratt (talk · contribs) 07:41, 10 November 2011 (UTC) As an obvious fan of Shellsort (the topic of my PhD thesis in 1971) I really wish I had the time to review this. Unfortunately it's going to be a while due to several prior commitments in areas unrelated to computer science.

The one thing I can say at this time is that Marcin Ciura does exercise due care in his judgements, which right there puts him in the sort of minority that you can take seriously. I've seen a lot of rubbish published in quality journals that is below his standards. --Vaughan Pratt (talk) 07:41, 10 November 2011 (UTC)

Failed. The article is riddled with uncited claims (see the no original research policy for details) as well as entire unreferenced sections (including a {{Citation needed}} tag in the lead); the sources themselves are OK and are of good quality, but virtually every claim made needs to be backed with reliable sources. Moreover, the prose also needs improvement across the board, in which a good copyedit for cohesion and prose quality are needed. Please work on getting everything sourced and the prose improved before renominating for GA again. Regards, –MuZemike 23:59, 6 December 2011 (UTC)

Invalid reference

Reference 21, "^ "kernel/groups.c". Retrieved 2011-03-30." is now invalid.

Since it appears to be a link to some linux kernel file or documentation for a specific file, it could be pointed to a more reliable source, like the own linux kernel page or some distribution page that holds the same file, like Debian (wich is heavily geared to developers). Or any other important distribution homepage.

The official kernel page can be used to access the linux source code tree. If someone can change the reference to point to:

http://git.kernel.org/?p=linux/kernel/git/stable/linux-stable.git;a=blob;f=kernel/groups.c

wich will show the source code. On the line 105 of this file begins the shellsort function.

Done, thanks for the link! MCiura (talk) 15:45, 6 February 2012 (UTC)

Vague complexity talk

This article is vague about just what kind of complexity it's discussing. Comparison complexity? Swapping complexity? Complexity is meaningless unless you're comparing measurements for the same thing.

Snarky example: Did you know that selection sort has a better worst case complexity than insertion sort? For swapping.

Will Faught (talk) 00:09, 21 September 2012 (UTC)

For typical "in-core" (in-RAM) sorting methods including Shellsort, there is only a constant factor difference between swapping complexity and time complexity, for both worst-case and average complexity. Hence the distinction is unnecessary for the asymptotic bounds of the form O(f(n)) and Θ(f(n)) treated by the article.

Your point is a good one for best-case complexity however, which for Shellsort is zero for swapping complexity but nontrivial for time complexity since any sorting method needs at least to examine every element. The article does not treat best-case complexity, but if it did, (a) swapping complexity would be too trivial to mention, and (b) the time complexity would be simply N times the number of gaps used, whether 2, 3, log N, or log² N.

Amusingly it follows from (b) that, asymptotically, my 2^p3^q variant of Shellsort has simultaneously the best worst-case time and the worst best-case time, presumably a rather rare property among the variants of a given algorithm (such as Shellsort) for a given problem (such as sorting) when there exist nontrivial variants. Vaughan Pratt (talk) 21:29, 21 January 2015 (UTC)

Actually, the gap sequence 1, 2, 3, 4, 5, 6, ... has the worst best-case time of O(n^2). — Preceding unsigned comment added by 2A01:119F:21D:7900:55E:4206:9AA6:8FFB (talk) 13:55, 13 June 2017 (UTC)

Graph of number of operations

The vertical axis on the graph says "log!2N" ... surely it should be "log2 N!" , i.e. the exclamation mark should be moved a couple of characters farther along. (132.244.72.6 (talk) 15:33, 15 November 2012 (UTC))

This appears to be a bug in the thumbnail generator. The label is correct in the original svg [1].—Emil J. 16:11, 15 November 2012 (UTC)

It appears correctly for me in the article. Using Chrome on Linux. Chris857 (talk) 16:23, 15 November 2012 (UTC)

Interesting. I’ve tried a different browser to double-check that it’s not a caching issue, but it’s not. Since you seem to be in the US, whereas me and the IP are in Europe, this would suggest that the problem is localized to the Amsterdam server cluster.—Emil J. 16:42, 15 November 2012 (UTC)

(edit conflict) I'm in the UK, so I should go through Amsterdam; but it looks OK to me in the article and on the file description page, at various resolutions. The SVG source reads as follows:

  <g transform="translate(23.0,141.4) rotate(-90)" style="stroke:none; fill:black; font-family:Arial; font-size:8.00pt; text-anchor:middle">
    <text><tspan>average number of element comparisons / log<tspan font-size="xx-small" dy="2pt">2</tspan><tspan font-style="italic" dy="-2pt">N</tspan>!</tspan>
    </text>
  </g>

Of this, the important bit reads

log<tspan font-size="xx-small" dy="2pt">2</tspan><tspan font-style="italic" dy="-2pt">N</tspan>!

where log₂ (2 being the base of the log) appear together, and the shriek is last of all. --Redrose64 (talk) 16:48, 15 November 2012 (UTC)

Now it works for me as well.—Emil J. 14:09, 16 November 2012 (UTC)

Now it works for me, too (I originally raised this on 15th November) and I'm using Explorer in the U.K. (132.244.72.5 (talk) 10:58, 23 November 2012 (UTC))

Rhoads additions

The two edits by GCRhoads give me pause. The performance claims seem to be based on a self-published blog, so I'm tempted to remove the edits due to WP:COI. Glrx (talk) 00:30, 18 June 2014 (UTC)

The order Rhoads gives in the article is misleading: it starts with "With respect to the average number of comparisons" and lists the sequences ordered by the sum of move and comparison counts (incidentally, a pretty arbitrary measure). Also, the average-case graph below does not show Rhoads' sequence. Also, I don't have my Knuth handy now, but I seem to recall that this sequence was already mentioned there (possibly in an answer to an exercise). Also, I don't see an explanation for Rhoads' removing the mention of Gonnet and Baeza-Yates' observation that optimal increments lie between 2.2 and 2.25. MCiura (talk) 11:01, 18 June 2014 (UTC)

• I agree with you. In fact, I was going to remove the Rhoads stuff per WP:OR, but I haven't had much internet access lately and it slipped my mind. Reyk _YO! 16:50, 18 June 2014 (UTC)
• I have reverted the edits. Glrx (talk) 18:27, 19 June 2014 (UTC)

Incerpi-Sedgewick Bound reproduced wrongly?

I just dug up the Incerpi-Sedgewick paper and am confused that the bound stated here is N e ^{sqrt(8 ln 2.5 ln N)} instead of N e ^{sqrt(8 ln 2 ln N)}. Also, the form stated in the article (N^{1+4/sqrt(2log₂N)}) appears to be better for comparison with the other bounds. Objections, anyone? --Björn — Preceding unsigned comment added by 204.120.71.252 (talk) 05:48, 25 June 2014 (UTC)

• I followed Knuth here. The complexity depends on the growth constant ρ, equal to 2 in the original paper and to 2.5 in the version of the sequence given by Knuth (it's overall better for ρ=2.5 due to a changed hidden factor in the big O). As to the N^foo form of the complexity, I'm all for the change. Thanks! MCiura (talk) 06:23, 25 June 2014 (UTC)

@MCiura: "I followed Knuth" == this result is as stated in TAoCP 3 ? (I don't have it, but I would like to add a reference...) --Björn 204.120.71.252 (talk) — Preceding undated comment added 06:30, 25 June 2014 (UTC)

• Yes, TAOCP 3. Cheers, MCiura (talk) 06:34, 25 June 2014 (UTC)

Pratt's gap sequence

Considering that inserting beyond 1 depth is not needed, and the amount of numbers in the gap sequence (all 3-smooth numbers), I think this gap sequence fits more in comb sort than in shell sort. 83.31.148.107 (talk) 08:43, 8 December 2017 (UTC)

The table lists two sequences from Pratt (71). There is one line on the graph labeled "Pr71". Could it be made clear which of Pratt's sequences this line relates to?108.171.128.180 (talk) 14:47, 3 July 2019 (UTC)

More Clear Animation?

The current animation, while accurate, does not visually display what operations it's taking. This could be confusing to readers who are unfamiliar with how the algorithm works. The animation on the article comb sort I think is a good example of showing what is being compared at each step of the algorithm. EstablishedCalculus 06:52, 24 May 2018 (UTC)

Pass-by-Pass Analysis

Has anyone ever analysed individual shellsort passes, rather than the statistics as a whole?

I am thinking of (1) net number of operations (number of comparisons, exchanges or moves) and (2) efficiency (number of moves or exchanges divided by number of comparisons)

I suspect that most passes would have similar statistics, but that the first pass or two (largest gaps) and possibly the last couple of passes (smallest gaps including 1) would differ from the main bulk of the passes. Has anyone ever looked at this to see what it tells us? It might show that the smallest gaps and the largest gaps have a greater effect on efficiency and might have to be chosen more carefully. 108.171.128.180 (talk) 13:45, 19 March 2019 (UTC)

Coprime

There is slight mention of coprime, but only slight. If there are sources commenting on its importance, they would be welcome.

FYI, starting with 1, then choosing the number nearest to 2.2× that is coprime to all previous (except the 1), is the sequence 1, 2, 5, 11, 23, 51, 113, 247, 541, 1189, 2617, 5761, 12671, 27877, 61331, 134933, 296843, 653057, 1436731, 3160811, 6953783, 15298321, 33656309, 74043881, 162896543, 358372411, 788419321, 1734522497, …. (Quickie calc: please check before using.) The article suggests that this might be good, but is too OR for here. JDAWiseman (talk) 15:13, 30 March 2019 (UTC)

I will weigh in here. I am the son of Donald L Shell the author of the Shellsort. In 1963 I wrote my first program, a sorting routine. When my father learned what I had chosen to code, he told me about his sorting routine. To explain how it worked he said that once a list had been sorted by an n-sort (using a gap of n) any other sort done after that retained the n-sort quality. Allyn Shell (talk) 05:13, 23 December 2023 (UTC)

He also indicated that the average difference between any two items in a random list is one third the length of the list. That is why picking a sequence which has each a gap of about one third of the prior gap is efficient. Allyn Shell (talk) 05:27, 23 December 2023 (UTC)

I will also say that because the Fibonacci sequence introduces a new prime number (as a factor) with every new number, I would recommend the sequence using every other Fibonacci number: 1, 3, 8, 21, 55, ..., starting with the largest number less than the size of the list being sorted. Also, noting that the lists stays n-sorted, the sort can make just one back comparison after an exchange (even if the back comparison leads to an exchange). That will significantly reduce the number of comparisons. Making the final 1-sort a simple insertion sort with as many back comparisons as necessary (there won't be many) will guarantee the final sort is complete. Allyn Shell (talk) 05:13, 23 December 2023 (UTC)

P.S. While I am commenting on dad's choice of gap sequence for his sort, he would often comment when asked about his sort routine that it was interesting to him that so many other people were able to get PHDs analyzing his routine when all he got were citations. Allyn Shell (talk) 05:48, 23 December 2023 (UTC)

Couple of ideas

I have been chasing the actual time taken on 5-6 million items and have 2 observations. I don't know if these are 'real improvements' or just 'on my compiler, on my computer, this runs faster'. I don't have the resources nor the theory to run it down.

first, the for (i = gap; i < n; i += 1) statement is significantly (5 to 10% depending on the sequence used) faster if changed to for (i = 1; i < n; i += 1).

second, the best sequence I have so far is 4.4 based, not 2.2 or 2.25 as suggested. The 4.4 one beats everything on the main page in my code. (that is 1, 4, 19,85,374,...). I have found that stopping the sequence or choosing from it works better at 10% .. that is, for 6 million, stop at the first term > 600k. The higher terms take longer than they contribute.

some numbers.. c++ standard sort, 0.65 sec for 6M above modified, 0.95 sec for 6m main wiki page code and sequences, 1.25 sec

4.4 was found by the computer, not selected. I ran every sequence from 2.0 to 7.0 multiple times on multiple test runs and 4.4 came out on top repeatedly. the worst sequences in those were the whole numbers (over 5 sec each for 2/3/4/5/6/7) which makes sense.

Maybe someone can make some use of these ideas.

Hello anonymous (please do end posts with four tildes). This is interesting. Two suggestions. Rather than the sequence {1, ⌊x⌋, ⌊x²⌋, ⌊x³⌋, ⌊x⁴⌋, ⌊x⁵⌋, …}, replace each term with the closest integer that is coprime to all previous gaps except 1. Also, don’t measure time, count comparisons. Please, given both of those, what’s the optimal x? JDAWiseman (talk) 13:17, 27 July 2019 (UTC)

O(N) for Shell's original sort

You give O(N) = N * N . for Shell's original sort. Surely that is not correct? A brain dead bubble sort will do that. I was under the impression, confirmed by doing some sorts by hand, that doing binary splits give N * log2 (N) — Preceding unsigned comment added by 2001:8003:E422:3C01:40ED:3437:1883:5670 (talk) 09:58, 26 December 2021 (UTC)

Graph of the number of operations again

It is displayed wrong in my Firefox and Opera. It looks like whatever reduces the size of SVGs, does not obey horizontal centering. The original file displays fine: [2] Gover7 (talk) 19:55, 21 December 2023 (UTC)

O(n log n) for Shell sort

Shell sort is proven to be faster than heap sort, which itself is O(n log n). However, no one agrees with me that shell sort is O(n log n) on average. Charles Chai (talk) 15:59, 23 July 2024 (UTC)