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 was delete. Nearly every, that means with the exception of a couple, of the keep votes are SPA accounts. Delete !votes are based in policy while at least one remaining keep !vote is WP:ILIKEIT. Consensus amoung editors is to delete. v/r - TP 21:51, 24 June 2011 (UTC)[reply]

Sleep sort

[edit]
Sleep sort (edit | talk | history | protect | delete | links | watch | logs | views) – (View log)
(Find sources: Google (books · news · scholar · free images · WP refs· FENS · JSTOR · TWL)

Absolutely no evidence whatsoever of notability. The cited sources are blog posts and the like. An amusing idea, but not of significance. JamesBWatson (talk) 14:34, 17 June 2011 (UTC)[reply]

Note: This debate has been included in the list of Computing-related deletion discussions. Cybercobra (talk) 00:50, 18 June 2011 (UTC)[reply]
Many sorting algorithms are linear time, such as the counting sort, the pidgeonhole sort and the radix sort. The issue is that comparison-based sorting algorithms can't be linear. So this is not an argument for delete, rather "strong" delete. Rgiusti (talk) 10:56, 18 June 2011 (UTC)[reply]
Those are not general sorting algorithms and only work for bounded integers. The "sleep time" is either unbounded or not an integer. Therefore the operating system scheduler will have to use a comparison sort. Therefore the algorithm cannot run in linear time. WP:OR was invented exactly to prevent the kind of argument we're having here, instead preferring the article to be deleted. —Ruud 11:05, 18 June 2011 (UTC)[reply]
Algorithms are a subject of theoretical computer science. An operating system clearly isn't, and the properties of an algorithm are only to be determined by their theoretical workings provided that certain requirements (e.g. the possibility to fork an arbitrary amount of processes and "sleep"ing for a determined amount of time) are given. Therfore, your argument is void. --Natanji (talk) 11:14, 18 June 2011 (UTC)[reply]
Then let's wait for the theoretical computer scientists to publish a few papers on this algorithm. In the mean time, it should not be here. —Ruud 11:28, 18 June 2011 (UTC)[reply]
The article pretty clearly states at the beginning of the analysis, "Assuming the sleep operation takes constant time", and then goes on to give a case where this is true (n interrupt timers), in which case the algorithm is pretty obviously linear time. 203.79.116.199 (talk) 12:43, 18 June 2011 (UTC)[reply]
Good example of why the article should be deleted. It has apparently mislead you into believing the algorithm has lower complexity. Any practical implementation, as given in the "Examples" section for example, will run in loglinear time or worse. Linear time can only be achieved using some theoretical oracle, whcih effectively does the sorting for you, or using special hardware and then still only approximately. None of this is discussed in the article, but quite essential for a correct and non-misleading description. We cannot do that however, because there are no reliable sources discussing these points. —Ruud 11:28, 18 June 2011 (UTC)[reply]
All of the issues you raise are discussed in the article, and from my reading you actually agree with his point (which is correct). The algorithm is theoretically interesting but practically quite silly- this is an argument to keep it not throw it away (Otherwise we would really only need three sorting algorithms on Wikipedia). 203.79.116.199 (talk) 12:43, 18 June 2011 (UTC)[reply]
No, these issues are not discussed in sufficient detail. No, they cannot be added, as neither you nor I are reliable sources per Wikipedia's standards. No, I do not agree with Natanji. Sleep sort is just a poorly specified insertion sort where sleep is a blackbox insert operation. We might just as well claim insertion sort runs in linear time under the, practically absurd, assumption that the in insert operation runs in constant time. —Ruud 15:29, 18 June 2011 (UTC)[reply]
I'm sorry but that comparison is complete nonsense. If it doesn't meet some arbitrary notability level that is fine, however someone having a fundamental misunderstanding of an algorithm is not a good justification for removing it (see: 4.133 billion years, "not linear time", "like insertion sort except not", etc...) — Preceding unsigned comment added by 203.79.116.199 (talk) 15:45, 18 June 2011 (UTC)[reply]
The problem is the topic is original research. This implies I cannot point you to any reliable sources to help you correct your misunderstanding of the algorithm. To prevent the endless and pointless discussion that will unfold in such a scenario, all articles on which no reliable sources exists will be deleted. —Ruud 15:51, 18 June 2011 (UTC)[reply]
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.