Wiki143:Articles for deletion/Rapid sort

The following discussion is an archived debate of the proposed deletion of the article below. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.

The result of the debate was Speedy Delete (db author). Tawker 17:34, 29 May 2006 (UTC)

Rapid sort

This is counting sort. The algorithm is poorly described here, and the author confessed to have invented the specific form and name of the algorithm described in this article on the talk page (a Google search - which is rather reliable in the area of computer algorithms - confirms that only Wikipedia talks about it under this name). Even if there were something new here, it definitely qualifies as original research. Also, er, for some bizarre reason the article text is an image. Deco 09:37, 28 May 2006 (UTC)

• Comment That surely is strange. Are you sure this is just an alias for counting sort? Medico80 09:56, 28 May 2006 (UTC)
  • Pretty sure, except the description is a bit vague. The author says he showed it to a friend who said the same thing, if that helps. Deco 09:58, 28 May 2006 (UTC)
• Delete – as original research, and duplication of existing stuff. And WTF is with that image? – Gurch 10:01, 28 May 2006 (UTC)
  • Just found out. Its Commons description page says "Picture of rapid sort descriptino to prevent vandalism." Yeah, and prevent editing - it appears User:Pce3@ij.net is trying out some weird ideas. Deco 10:30, 28 May 2006 (UTC)

    There is a similar statement on Talk:Optimal_classification#Cleanup; I think this user honestly believes this is an issue. It's easy enough to replace the image by something else, either in the article or on the image page, so I don't see how this is an issue one way or another. --Lambiam^Talk 13:42, 28 May 2006 (UTC)

    I've replaced the images by text, easy enough to do, which incidentally also improves the layout. --Lambiam^Talk 13:56, 28 May 2006 (UTC)

• Question. Isn't what is described here a counting variant of Pigeonhole sort? I tried to read Counting sort and it seems different, but I find it hard to understand. After a brief and ambiguous explanation in the lead paragraph, the only description is in C code with so many intrusive low-level comments that I get lost when looking at the actual code. --Lambiam^Talk 13:42, 28 May 2006 (UTC)

You guys can delete it or whatever you want to do. I tried to research the counting sort after Black said that's what it was just as I did when someone claimed it was a bucket sort about ten years ago. I have no doubt that someone else has discovered it long before me but I haven’t been able to find that out either. As for it being original research as the basis for its deletion go ahead I can't prove that it is not and in fact I worked on it for a very long time before it became the sort you now see. This raises another question. I thought that no original research applied only to a situation in which the claim about the research was invalid or could not be verified versus simply the person who did the work or made the discovery not publishing it on the Wiki. I mean if something is verifiably correct then what's the problem? Oh well bottom line for me is that the Rapid sort is what I ended up with when I tried to improve another sort after many, many, many days and nights and weeks and month trying to make that other sort better. Okay so do whatever you guys want it truely makes no difference to me. ...IMHO (Talk) 18:25, 28 May 2006 (UTC) PS By the way I just through that part in there about it being a variation of the Pigeonhole sort but honestly I have no idea. I was just in a hurry to get it posted so I could go on to something else. My guess is that you guys will figure out what to do without any further help from me. ...IMHO (Talk) 18:49, 28 May 2006 (UTC)

Hi Pce3. I realize it's disappointing, but regardless of its veracity it really does still qualify as original research, because it's a publication of your own ideas that have never before been exposed in any other forum to public scrutiny. Also, I'm pretty much certain it is exactly counting sort, which is an O(n) time sort, and is often the best choice of sort for elements with a very small range like your 1..4 numbers. It's not used in place of sorts like quicksort because it doesn't work well for elements that take on a very large range of values, such as arbitrary 32-bit integers - the array would have to have 2³² entries. I agree that the counting sort article could definitely use some work. Deco 18:51, 28 May 2006 (UTC)

Again if you guys want to deprive others of the knowledge of this sort then go ahead. It does not matter to me. As for previous publication I published it on the Internet in at least 1996 and the only response I got was an email suggesting it was a bucket sort and I have never heard of a counting sort prior to hearing about it here. So as tight lipped as the ACM and IEEE and other such organizations are it could very well have been created and filed away long before my efforts resulted in its creation back in 1972. so have at it. If you don't want others to know that it exists fine with me. Hide it, burry it, paint it do whatever you want I can still enjoy the very elegant result of my hard labors without any further ado. Whatever you decide will only make a difference to others and will not make any difference to me. 19:08, 28 May 2006 (UTC) And PS again... As for being a memory hog that it is but then imagine an Internet protocol (why they didn't think of this one back then is a stretch for me) like a the echo of time or quote for sorting on the basis of the Rapid sort such that you simply enumerate you data like converting an "A" to ascii 65 and then using that enumeration as an Internet address which when done returns a count. Doing it that way would allow you to avoid incrementing through all of the addresses that had zero count values. Call it the Sort Port! When used properly the Internet can be a great place! ...IMHO (Talk) 19:22, 28 May 2006 (UTC)

Also I now have a "new" category name for this sort. I now call it an address sort. ...IMHO (Talk) 19:34, 28 May 2006 (UTC)

Please refrain from creating redirects (address sort) for names that you invented - there isn't really a standardized name for a search that depends on indexing using element values, although maybe there should be. I would just call them "indexing-based searches" - there's a table of them at sorting algorithm that you edited. I'm afraid I don't quite understand your Internet protocol analogy, but the ideas of radix sort generalize counting sort in a way that eliminates the large memory requirement by looking at a single "digit" at a time. Deco 19:59, 28 May 2006 (UTC)

• Weak Delete unless the notability of this sorting method can be shown. There are literally thousands of sorting methods, many are very obscure variants. I do not know if this is obscure or not, but the burden of proof is on those who wish to keep an article in cases of notibility. HighInBC 18:55, 28 May 2006 (UTC)

• Strong Not Delete Why? It occurs to me that while I don't care for myself if the article is deleted that I do care for anyone who might want to further research the possibility of overcoming the "zero" problem such as by the method of time delay or who knows what someone might come up with? For this reason I think you need to leave this article alone especially since the sort can be implemented in hardware where the "zero" problem can be handled in a different way than with software and where even incrementing through all of the zeros will be accomplished exceptionally fast. Think in terms of a sort chip, if you will. I am also including here below the discussion with DECO he moved to my talk page. ...IMHO (Talk) 21:44, 28 May 2006 (UTC)

• • If you're interested in sorting hardware, see sorting networks, which are exponentially faster than the solution you describe (O(log n) sorting time). Deco 22:05, 28 May 2006 (UTC)

• • A hardware sort based on sending the data to the address bus of a random access memory is far superior to and different from a sorting network which is defined as follows: "A sorting network is an abstract model of a network of wires and comparator modules that is used to sort a sequence of numbers." Unlike the "sorting network" the Rapid sort (or Instant sort as is the name of its hardware version) is not an abstract model but a real and working hardware based sort routine which can blow away any other sort you can come up with whether hardware based or not. ...IMHO (Talk) 04:19, 29 May 2006 (UTC)

(The following discussion with DECO is being moved from my talk page to here.) ...IMHO (Talk) 21:44, 28 May 2006 (UTC)

Some more details on counting sort

Hi Pce3. Just to emphasize that I harbour you no ill will, I've scanned a description of Counting Sort from the seminal textbook Introduction to Algorithms. They don't cite a particular researcher who came up with it, but the book was first published in 1990 and mostly describes classical results from the 1970s. I think if you take a little time to read it you'll realize that what it describes is very much the same idea that you describe. Bucket sort and pigeonhole sort are variations on these ideas. If you'd like to incorporate some of your ideas or implementations into the counting sort article, that would be great. Please keep editing, and keep thinking about algorithms too! Deco 19:48, 28 May 2006 (UTC)

Thanks for your research efforts on my behalf but I have already decided to reclassify the Rapid sort as an address sort. Thanks anyway. I will however read your material. Thanks. ...IMHO (Talk) 19:52, 28 May 2006 (UTC)

Okay I've looked at the material and here is my conclusion. My work on the rapid sort began with an effort to improve the Shell-Metzner sort. I wrote this up when I published it on the Internet in 1996. I may even have a record of each step that was taken but they led me to this idea of simply using the data to address memory. Although there is a similarity with the counting sort in that the data in one array is used as an index in another array which is incremented the difference is that my goal was to both maximize speed and to achieve ultimate simplicity since at that time my favorite endeavor was logical equation reduction. Since I had already started from a sort that compared data I was enthused when it turned out that what I was working with did not require a comparison at all. Furthermore since my goal was to eliminate excessive baggage I in fact recall abandoning the idea of using more than one array or even a multi-dimensional array to accomplish the sort. My goal was to reach an end point which this sort represented rather than to then expand upon this idea and add multi-dimensions or other arrays, etc. Why you ask? Again my goal was to find the ultimate sort which the Rapid sort represents. ...IMHO (Talk) 20:15, 28 May 2006 (UTC)

There are some implementation differences - namely, you directly use the input list as it is generated instead of an input array, you print your output instead of storing it in an output array, and you don't perform the intermediate loop on the array which the book is just showing for exposition (most implementations I've seen don't have it). But these are not big differences. As you can see, they also don't use comparisons or multidimensional arrays either. I understand that you're very attached to this algorithm that you've committed a lot of time to thinking about, but it's really nothing new and it's not appropriate for sorting elements that take on a large number of values, not only because of the memory required for the array but because of the time required for the final loop. There is no simple way to "remove the zeros" without increasing the complexity. Deco 20:23, 28 May 2006 (UTC)

Well you have not read my further reply to this argument on the Rapid sort deletion talk page so I will repeat it here. Assuming that even though there may not be a client computer or server with a Sort port (similar to an echo or quote port) such capability can be provided by even the router that is home for a particular range of addresses. The idea being that the router or server or client computer returns a count that corresponds with each [identical] address that was sent. The trick then becomes how to get the counts back in sequential order. This can be accomplished simply by implementing return of the count on the basis of a schedule derived from the address [(converted data)] that was sent with a sufficient interval to overcome all types of potential delay. The same scheme could be [implemented] locally and even within the same computer that sent the data as an address with far more certainty [and precision] of the interval being long enough. Instead of an address sort you could call this a time delay sort. Also did I mention that I implemented this sort using random access memory and that an integrated chip that would do test for none zero memory and do the incrimination as well would probably beat any other method that can be implemented in hardware or software? ...IMHO (Talk) 20:57, 28 May 2006 (UTC)

If you'd prefer to discuss it here that's okay. First I'll say that even if this "port sort" idea were novel research, it still counts as original research - we describe things that are well-known (see Wikipedia:Notability), not things that we come up with on our own. For sort algorithms, this usually means they have to be published in a reputable, peer-reviewed journal or conference.

As for the idea itself, it's a fun idea, but unfortunately does not yield a speed improvement - the key problem is that the nodes are unaware of one another. Just think of the case where there's two values, one the smallest and one the largest. The largest could not send its count as soon as the smallest has finished, because it doesn't know that the nodes for the intervening values don't have counts to send. To be correct, they'd each have to be allocated a time slot, requiring the same time as counting sort. Besides the fact that overhead makes it entirely impractical. Deco 22:02, 28 May 2006 (UTC)

(End of discussion move.)

Only sort routine that can be implemented directly in hardware...

Why would anyone want to delete an article about the only sort routine that can be implemented directly in hardware? ...IMHO (Talk) 22:44, 28 May 2006 (UTC)

Except it's not. It's not even a particularly good hardware sort algorithm. Deco 03:09, 29 May 2006 (UTC)

Except? You forgot to show an actual exception much less a superior (and actual) hardware sort. You ever build a hardware sort? I didn't think so. ...IMHO (Talk) 03:59, 29 May 2006 (UTC)

Also everyone please comment on whether you think this method qualifies as original research or whether it qualifies as a counting sort. Thanks. ...IMHO (Talk) 01:27, 29 May 2006 (UTC)

• Delete. This is just a special case of counting sort and has no interesting features. It's usefulness is limited by assuming that the data consists only of keys, and not of records that include a key together with other things. That assumption is the only reason it looks simpler. I've used exactly this method in programs since the 1970s and I'm certain that I didn't think of it first either. McKay 06:36, 29 May 2006 (UTC)

Already Deleted B.Wind 15:59, 29 May 2006 (UTC)

The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.