Talk:X + Y sorting

GA Review

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

Reviewer: N8wilson (talk · contribs) 14:25, 14 June 2021 (UTC)

GA review – see WP:WIAGA for criteria

---

Thank you very much David Eppstein for your significant contribution to this article which has taken place over the course of nearly a year. It's come quite a long way from where it used to be before you started editing. That work is greatly appreciated!

As I work through the remaining criteria below, I'll post updates accordingly. Barring any unexpected developments reviews are typically completed within 7 days. --N8 14:25, 14 June 2021 (UTC)

1. Is it well written?

   A. The prose is clear and concise, and the spelling and grammar are correct:

   16:45, 24 June 2021 (UTC) Closing per 2nd opinion below.

   18:21, 15 June 2021 (UTC) Held per contested review; see discussion below

   14:34, 15 June 2021 (UTC) No obvious issues with spelling or grammar but the article needs further work to be understandable to an appropriately broad audience. Many of the formulas and technically notated elements are accompanied by explanatory supplements which mostly work the article's favor for this criteria. Nonetheless, as currently written the article—especially the orderings and comparisons sections—will be difficult for readers who are not (pretty deeply) familiar with time complexity, combinatorics, and the general principles of algorithm research and design. In fact, there are really two topics covered by the title of this article: 1) the X+Y sorting problem itself and 2) the problem of developing an algorithm with a lower bound to solve X+Y sorting or proving that no such algorithm exists. Both of these would feasibly be covered to some extent in an undergraduate curriculum on computer science. By that measure, WP:ONEDOWN suggests targeting an audience with a secondary education to the extent possible. However, the topic—particularly the second problem of bounding complexity—might be covered in greater depth in a postgraduate curriculum and indeed as an unsolved problem it likely attracts interest from the most advanced experts in the field. The challenge in an article such as this is to highlight in plain language the most notable aspects of the topic and proceed with progressively deeper levels of detail in a way that does not alienate lay readers too soon. To this end, a concrete example of the X+Y sorting problem itself would significantly improve the article. (Something small like X=[2,4,8],Y=[10,11,12].) In its current state, the article gives coverage primarily to the problem of limiting complexity for algorithms that solve X+Y sorting but little care to helping the reader conceptualize the X+Y sorting problem itself. The clarity would also be improved for most audiences by moving proofs and mathematical justifications after primary claims sourced from research. For example, the statement "the set $X+Y$ has $O(n^{8n})$ different possible sorted orderings" gets "buried" by its positioning after the math that justifies of it. That fact would be suitable to begin the section on orderings, followed by a brief explanation of what it means for lay readers, then why it's relevant to the unsolved problem, and lastly how it's justified. Similarly, the applications of the problem may be of greater relevance to most readers and could arguably be moved forward. Concepts such as high dimensional spaces with hyperplanes are useful only to the most technical readers. Since these individuals are likely to seek such information about this topic in published research papers or textbooks it can safely be de-emphasized in the coverage on WP. This isn't meant to suggest that any content needs to be removed, only that the topic covered here permits a more understandable explanation which should be addressed before classification in the GA class. In particular, this brief section on Technical content assistance captures the notion well.

   B. It complies with the manual of style guidelines for lead sections, layout, words to watch, fiction, and list incorporation:

   14:34, 15 June 2021 (UTC) A case could be made for some minor improvements to phrasing in the lead to accommodate wider audiences but not a strong enough case IMO to disqualify GA class. Layout and words to watch usage follows MOS. Fiction and list guidance n/a.

2. Is it verifiable with no original research?

   A. It contains a list of all references (sources of information), presented in accordance with the layout style guideline:

   23:15, 15 June 2021 (UTC) pass; technical consistency not applicable to standard

   14:34, 15 June 2021 (UTC) There are no concerns with the list of references. Technical note: The article contains mixed use of inline citations with and without the use of <ref>...</ref> tags resulting in both footnotes and prose-linked references. The use of {{harvtxt}} outside of <ref>...</ref> tags has been deprecated on WP (see template page). These should be migrated to use the same style of referencing elsewhere in the article as consistency in this aspect is part of the style guideline.

   B. All in-line citations are from reliable sources, including those for direct quotations, statistics, published opinion, counter-intuitive or controversial statements that are challenged or likely to be challenged, and contentious material relating to living persons—science-based articles should follow the scientific citation guidelines:

   14:34, 15 June 2021 (UTC) Sources are reliable and I did not find any statements likely to be challenged. Citations follow appropriate formats inline but would benefit from consistency as indicated in part A above. References include appropriate identifiers where applicable.

   C. It contains no original research:

   16:45, 24 June 2021 (UTC) With spot checks, closing per 2nd opinion below.

   Seems very unlikely given the sources and claims but a thorough check was not completed.

   D. It contains no copyright violations nor plagiarism:

   16:45, 24 June 2021 (UTC) As per previous comments and quick scan, there are no concerns here.

   Seems very unlikely given the sources and claims but a thorough check was not completed.

3. Is it broad in its coverage?

   A. It addresses the main aspects of the topic:

   16:45, 24 June 2021 (UTC) Closing per 2nd opinion below. AGF applies to some sources.

   Although not thoroughly evaluated, as noted for criteria 1 above the article would benefit from giving the base X+Y sorting problem more attention early in the article. More technical readers may also appreciate coverage of any implications of resolving the open question on complexity. What complexity class does the problem fall into? Are there other notable problems reducible to X+Y sorting that benefit from progress toward this question? This receives some incidental coverage, or is hinted at in the 'applications' and 'related problems' sections and may already be covered to the extent possible using available sources.

   B. It stays focused on the topic without going into unnecessary detail (see summary style):

   16:45, 24 June 2021 (UTC) Closing per previous comments; no concerns.

   Level of detail included in this article is helpful to readers with deep expertise. It probably does not need to be reduced or trimmed back as it does not detract from developing an understanding of the topic for those readers. On the contrary, those details help clarify the notability within the field. There are concerns that the presentation of this level of detail may interfere with the readability for non-experts however this is addressed by other criteria.

4. Is it neutral?

   It represents viewpoints fairly and without editorial bias, giving due weight to each:

   14:34, 15 June 2021 (UTC) uncontentious topic and language is appropriate and un-opinionated.

5. Is it stable?

   It does not change significantly from day to day because of an ongoing edit war or content dispute:

   14:25, 14 June 2021 (UTC) Closest thing to edit warring or dispute appears to be minor confusion with a bot over an hdl ref. [1] There is no concern about stability.

6. Is it illustrated, if possible, by images?

   A. Images are tagged with their copyright status, and valid fair use rationales are provided for non-free content:

   14:25, 14 June 2021 (UTC) This is a technical pass on the basis that it's unlikely non-free images currently exist for such a specialized subject. A cursory search came up empty in commons and on the web within appropriate licensing constraints. However, the nature of this topic is such that a relevant image or illustration would significantly improve the clarity of the article if one can be obtained.

   B. Images are relevant to the topic, and have suitable captions:

   14:25, 14 June 2021 (UTC) n/a per above

7. Overall:

   Pass or Fail:

   16:45, 24 June 2021 (UTC) Thanks to Urve for providing second opinion. All criteria appear to be met. Will circle back shortly to perform remaining cleanup for moving to GA.

   14:34, 15 June 2021 (UTC) Pinging David Eppstein for completed review. Primary observed gap for GA class is a shortfall in addressing "as broad an audience ... as possible" as part of criteria #1. Portions of the content meet this standard in isolation but on the whole the article still has room to improve. Writing for less technical audiences is also likely to expand coverage of a key element of the main topic: the X+Y sorting base problem itself rather than the problem of constraining the running time of algorithms that solve it. A pass/no-pass assessment was not made for all GA criteria at this time. --N8 14:34, 15 June 2021 (UTC)

@N8wilson:: I think this review, asking for a lay-level article on a research topic and asking for the removal of the research aspects of the topic from the article, is completely inappropriate. It is possible that aspects of the topic can be made more accessible. Nevertheless, as a topic whose primary interest is researchers, WP:ONEDOWN suggests that it only needs to be made accessible to undergraduate computer science students. Your suggestion to remove more advanced material would destroy the main point of the article, lobotomize Wikipedia, and make it a place that is hostile to technical content. I am also extremely unimpressed with the way you quick-failed the article, without providing me any opportunity to respond, and without addressing any of the quick-fail GA criteria. The normal course of a review, for an article that can be brought into compliance with the GA criteria, is to put the article on hold and provide the editor a chance to respond and clean up any issues. Quick fail is only for articles that are very far from GA, so far that they cannot be brought into compliance with such a period of editing. Please reconsider your actions. —David Eppstein (talk) 17:20, 15 June 2021 (UTC)

Additionally, it is false that the use of harvtxt in inline text has been deprecated. What has been deprecated is non-textual inline citations of the form (Author Year). The RFC explicitly did not come to a consensus on in-text callouts of authors and years, as part of the article text rather than as a reference, to provide information to readers about who did what when rather than purely for verification. It was about referencing, not about writing style of in-text descriptions of the history of a topic. Therefore, your concerns about referencing style are misplaced. I believe the citation style is fully consistent: all references are in footnotes in Citation Style 1, and those instances of harvtxt in the article text are part of the article text and are not intended as references (you can tell because the parts of the article that include them still have footnotes). But even consistency of citation style is not part of the GA guidelines, which require only that citations comply with the section layout guidelines and that they be to reliable sources. —David Eppstein (talk) 18:48, 15 June 2021 (UTC)

@N8wilson: I believe I have addressed all valid concerns:

• Application section moved forward and lead section rewritten to reflect the new order of topics
• Small example instance added to "Problem statement" section, and re-used to better explain the polynomial multiplication application
• "Number of orderings" section content re-ordered and reworded to put the bound up front before the details of its proof and better explain its significance

The review has not provided any specific issues needing addressing in the "Number of comparisons" section, which remains largely unchanged. As discussed above, I do not consider the use of {{harvtxt}} within the article text to be a valid referencing concern (any more than is non-templated wording like "by Elwyn Berlekamp prior to 1975" or "Steven Skiena recounts", or the use of other templates in the text of other articles such as {{as of}} or {{convert}}) and I have not made any changes triggered by this invalid non-problem. —David Eppstein (talk) 19:48, 15 June 2021 (UTC)

@David Eppstein: I was happy to re-open this nomination. The primary concern that stood out to me at the time of the review is also listed as requirement #6 for B-class articles. That made closing the review seem like an appropriate course of action but I understand the normal course is different and I won’t be one to shut down productive discussion if there’s an opportunity for it. Re-opening is easy; thank you for requesting it.

First let me clarify that I never (intentionally) suggested the removal of any material. I suspect this is just a case of reading quickly as the only phrase mentioning removal says exactly the opposite: removal is not suggested. That sentiment is again echoed in part 3.B. of my review indicating that the advanced content is helpful and should stay. I would be upset too if somebody suggested removing quality content from WP - especially given that it’s reliably sourced - but as best I can tell, I didn’t do that. In short, I think you and I actually agree on this point.

My suggestions included de-emphasizing the most advanced content, re-organizing it, and supplementing it with content better suited to a broader audience. I think the "broadest possible audience" is where you and I might see this topic differently. WP:ONEDOWN is a starting point and I tried to make clear above that it’s particularly tricky for a topic like this that may be commonly studied at both the undergraduate and postgraduate levels. To me this means WP editors should try to make as much of the topic as possible accessible even to readers exposed to the science at the level of a secondary education.

Let me apologize for the confusion regarding {{harvtxt}}. You’re correct that there are no GA-related problems with this and in particular, the last sentence I wrote in that section was poorly worded and incorrectly applies the consistency standard to the technical implementation of references; I’ve stuck that portion accordingly. To clarify the remaining bits, I didn’t say this is deprecated for inline citation but rather that the template page indicates its use outside of <ref>...</ref> tags is deprecated. This doesn’t need fixing for GA (possibly at all?) but I presume there was some technical reason that the template indicates usage inside ref tags is preferred and it seemed worth noting if only for awareness.

I think the best course forward at the point would be to solicit some additional feedback. I'd encourage you to mention the nomination to editors you think may be able to help. Thank you again for continuing to work on this content. IMO, the changes you made have already helped improve the accessibility. --N8 23:15, 15 June 2021 (UTC)

The template documentation correctly says not to use {{harv}} outside of ref tags. I am not doing that. The article uses {{harvtxt}}, a different template that produces different output but shares the same documentation page. The difference between those two templates is that {{harv}} is intended purely for referencing but {{harvtxt}} is intended for in-text call-outs to sources. As for requesting additional opinions: that is generally the call of the reviewer rather than the article editor, and instructions for doing so can be found at WP:GAN/I#2O. —David Eppstein (talk) 00:57, 16 June 2021 (UTC)

You're right. I read right through that and missed the difference. Thanks. Nomination is listed for second opinion. --N8 01:03, 16 June 2021 (UTC)

Thanks. Anyway, I'm not entirely sure what a second opinion is supposed to bring. I have made all of the valid specific changes you suggested, and the remaining suggestion, that I refocus the entire article from being about the research topic that it is into a different and non-existent topic, the undergraduate-level study of practical methods for this problem, is impossible to do. The whole point of the article is that we don't actually know anything better than just using a general-purpose sorting algorithm, so there are no practical methods in wide undergraduate study to refocus the algorithm on. The only undergraduate-level work that I know of that even touches on this topic is Skiena's, which (despite being a good book) is a bit outside the mainstream undergraduate curriculum, and touches on this problem only briefly in a case study. There's a reason that almost all of the sources here are research papers. —David Eppstein (talk) 18:28, 16 June 2021 (UTC)

Incidentally, I have now added an image to the article. I'm not sure it does "significantly improve the clarity of the article" but I think it at least may provide some valuable intuition to some readers. It's just of the example input and output, visualized in a different way — I didn't try to draw the cell-counting lower bounds because for that part of the article, the smallest case that's not completely trivial is $n=2$ and already leads to four-dimensional cell-counting, difficult to draw. And I'm not convinced that trying to animate Lambert's algorithm would help much (nor am I set up to create animations easily). —David Eppstein (talk) 06:56, 19 June 2021 (UTC)

@N8wilson: I do not entirely understand what the second opinion is asking for. If the issue is the accessibility of the prose to a general audience, that is not possible. The guideline suggests we make it as accessible as possible, and it seems to be so. The Klarreich article highlights the difficulty of writing in this domain, omitting almost all details in exchange for accessibility. We are guided by the sources, and if they are difficult to follow for a layperson or an undergraduate, WP:DUE requires we follow them anyway. I think the article is in as good of shape as can be in terms of accessibility.

If your concern about technical accessibility is harvtxt, I think David is correct on this.

I did a few random spot-checks and there seems to be no original research and the sources adequately support the statements. Urve 02:18, 24 June 2021 (UTC)

@Urve: Thank you. I'll wrap this review up shortly. --N8 16:29, 24 June 2021 (UTC)