Wikipedia:Articles for deletion/Radix Selection

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 keep. Mojo Hand (talk) 14:45, 6 December 2025 (UTC)[reply]

Radix Selection

[Hide this box] New to Articles for deletion (AfD)? Read these primers!

(Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL)

WP:NOR. Bogus claims (to start with, radix sort is not $O(n)$ time and neither is this) sourced only to a blog post. This was draftified only to be re-created, with the same text and added references that may be about radix selection algorithms in general but that do not support the content of this article (because the content is the same as Draft:Radix Selection which was based only on the blog post). —David Eppstein (talk) 07:35, 14 November 2025 (UTC)[reply]

Order of run-time has been corrected to be the same as Radix Sort -

O(n\cdot w)

. Blog post reference has been removed. All other references support Radix Selection and describe it in the same way, especially the first paper. These describe Radix Selection, Bucket Selection and Bitonic Selection algorithms. The third reference describes binary-Radix-Selection algorithms and describes is similarly as this article. Several referenced papers not only describe k-th element selection, but also top-k element selection, where the top-k elements don't have to be in sorted order. All of these papers show superior performance for Radix Sort, since Radix Selection does less work. Duvavic1 (talk) 14:24, 14 November 2025 (UTC)[reply]

Why do we need an article on a subpar nonlinear selection algorithm when linear ones are available? Also the way you have written the time bound now is worse than n log n since n distinct keys need word length log n. —David Eppstein (talk) 19:14, 14 November 2025 (UTC)[reply]

Median-of-Medians is only theoretically linear and interesting from theoretical point of view only, which Cormen and Sedgewick books state, as its constants are very large with practical implementations only used as a fallback to the quickselect algorithm to protect against cases which go O(n^2) - e.g. introselect in C++. Radix Sort is the fastest practical sorting algorithm that GPU vendors implement (29Gig/sec of random 32-bit values), which also parallelizes well. Radix Select is faster than Radix Sort by several times in practice and also parallelizes well. This is the reason Alibaba engineers switched to it. For the order, w = 4 for 32-bit elements and w = 8 for 64-bit elements. For and array with million elements logn = 10 and for billion elements logn = 20, with Radix Sort/Select winning, which is measurable with real benchmarks, where nlgn sorting algorithms loose in performance to Radix algorithms at about 10K-100K elements in practice. Duvavic1 (talk) 22:34, 14 November 2025 (UTC)[reply]

In my analysis Radix Sort processes 8-bits at a time, while it is also currently practical to process between 8-16 bits at a time, per pass. Duvavic1 (talk) 22:40, 14 November 2025 (UTC)[reply]

When did I say medians of medians was the right practical choice? Quickselect is much better. —David Eppstein (talk) 23:00, 14 November 2025 (UTC)[reply]

Quickselect is a great algorithm, with O(n^2) cases always lurking as a possibility with adversarial inputs. Sedgwick suggests randomizing the input array to reduce the chance of hitting such a case, or using Median-of-Medians as a safety net. In practical benchmarks Radix Select beats quickselect in performance for 32-bit keys, lends itself well for parallel implementations, such as GPUs, and is has an interesting algorithmic connection to Radix Sort, just like quickselect has to quicksort, and Bucket Select to Bucket Sort. Duvavic1 (talk) 23:32, 14 November 2025 (UTC)[reply]

Oops, for 1K elements logn = 10, for 1Mega elements logn = 20, for 1Giga elements logn = 30 Duvavic1 (talk) 00:28, 18 November 2025 (UTC)[reply]

This algorithm is fairly new with little literature coverage, but falls out naturally from MSD Radix Sort. It deserves notice because for constant size keys it's linear time in the worst case. QuickSelect is O(n) in the expected case and O(n^2) in the worst case, while Median-of-Medians is slow in practice while being theoretically O(n). Another natural benefit of Radix Select is its natural handling of duplicates, since they end up in the same bin. Duvavic1 (talk) 01:30, 25 November 2025 (UTC)[reply]

Note: This discussion has been included in the list of Mathematics-related deletion discussions. WCQuidditch ☎ ✎ 20:09, 14 November 2025 (UTC)[reply]
Keep. I agree the article wasn't in a great state to begin with; I've reworked the lede extensively and found citations for the (previously unreferenced) in-place algorithm description. Still needs a lot of polish, but I don't think OR should be a concern now. Would also like to add a section on GPU-parallel variants (algorithm isn't just theoretical, it's in use by NVIDIA), but that's a content-improvement issue, out of scope of the AfD discussion here. Preimage (talk) 01:02, 20 November 2025 (UTC)[reply]

Relisted to generate a more thorough discussion and clearer consensus.
Relisting comment: Any further thoughts?
Please add new comments below this notice. Thanks, CycloneYoris ^talk! 01:05, 22 November 2025 (UTC)[reply]

Tentative Keep. I know nothing of the topic, but a scan of the sources seems to sustain the notion that the topic is notable and sufficiently covered in the scientific literature (presumably only following Preimage's update, but hey). - Main body section needs more sourcing, and title needs downcasing. --Elmidae (talk · contribs) 14:25, 24 November 2025 (UTC)[reply]

Relisted to generate a more thorough discussion and clearer consensus.
Please add new comments below this notice. Thanks, Sandstein 07:44, 29 November 2025 (UTC)[reply]

Keep The topic got in-depth coverage in the academic literature. Kelob2678 (talk) 21:27, 1 December 2025 (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.