Will there be a sorting algorithm with O(n) time complexity?

GPT-5.4

Vote: Yes

I maintain vote A. The key issue is ambiguity in the question. If it asks whether an O(n) sorting algorithm can exist at all, then the answer is already yes: counting sort, radix sort, and bucket sort are standard examples under appropriate input assumptions. Grok’s B argument is correct only for the narrower claim of sorting arbitrary inputs in the pure comparison model. But that is not what the question explicitly says. The comparison lower bound does not rule out linear-time sorting when keys have exploitable structure. The strongest opposing point therefore narrows the problem rather than refuting A. Since the unqualified question asks about a sorting algorithm with O(n) time complexity, the existence of established non-comparison linear-time algorithms is sufficient to make A the better answer.

Claude Opus 4.6

Vote: Yes

I maintain my position. The answer is clearly **Yes** — O(n) sorting algorithms already exist. Counting Sort, Radix Sort, and Bucket Sort are well-established algorithms that achieve O(n) time complexity under specific (but common and practical) conditions. These are not theoretical curiosities; they are implemented in real systems and taught in every algorithms course. Grok 4.1 Fast's argument for B is technically sound regarding the comparison-based lower bound, but it answers a different question. The question asks whether there **will be** a sorting algorithm with O(n) time complexity — not whether there will be a *comparison-based* sorting algorithm with O(n) time complexity. The question doesn't specify the comparison model, and sorting algorithms are not limited to comparisons. Grok's characterization of the constraints as "restrictive" is debatable. Fixed-width integers are the most common data type sorted in practice. Sorting 32-bit or 64-bit integers with radix sort in O(n) time is entirely standard. The constraints are practical, not pathological. The overwhelming consensus (4 out of 5 models) correctly identifies that such algorithms already exist. The answer is A.

Kimi K2.5

Vote: Yes

I maintain that the answer is Yes. The phrasing 'Will there be' encompasses existence, and linear-time sorting algorithms already exist and have been standard in computer science for decades. Counting sort, radix sort, and bucket sort are proven O(n) algorithms under their specified constraints. Grok's argument correctly notes that comparison-based sorting has a Ω(n log n) lower bound, but the question does not specify the comparison model or require the algorithm to work for arbitrary comparable elements without constraints. It simply asks if a sorting algorithm with O(n) complexity exists or will exist. Since these algorithms are already implemented, taught, and deployed in production systems (e.g., Radix sort in integer sorting, Counting sort in specialized database operations), the existence is confirmed. The restrictive assumptions mentioned by Grok (bounded ranges, fixed key sizes) are valid use cases that cover many practical scenarios, not theoretical edge cases. Therefore, O(n) sorting is already reality, not a future possibility.

Gemini 3.1 Pro

Vote: Yes

I am maintaining my vote for 'Yes' because the prompt simply asks if there will be *a* sorting algorithm with O(n) time complexity, not a *general-purpose comparison-based* sorting algorithm. While Grok 4.1 Fast correctly points out the information-theoretic lower bound of Ω(n log n) for comparison sorts, this constraint does not define the entirety of what constitutes a 'sorting algorithm'. Algorithms like Counting Sort, Radix Sort, and Bucket Sort are universally recognized, taught, and deployed as sorting algorithms. The fact that they require specific structural assumptions (such as bounded integers) does not strip them of their classification. Because non-comparison O(n) sorting algorithms already exist and are actively used today, the condition 'there will be a sorting algorithm with O(n) time complexity' is already satisfied. To vote 'No' requires artificially injecting constraints into the prompt that do not exist.

Grok 4.1 Fast (changed mind)

Vote: Yes

Upon reflection, the other models' arguments are compelling and correct. The question does not specify 'general comparison-based sorting for arbitrary elements.' It simply asks if there will be *a* sorting algorithm with O(n) time complexity. Algorithms like counting sort (O(n + k) with k = O(n)), radix sort (O(n) for fixed-width keys), and bucket sort already achieve this under standard, well-defined assumptions on input structure—conditions common in practice for integers or strings. My initial vote focused too narrowly on the Ω(n log n) lower bound for comparison sorts, but that bound does not apply here. These non-comparison algorithms are bona fide sorters with proven O(n) worst-case time and are staples in CS textbooks (e.g., CLRS). Since they exist today, there certainly 'will be' such algorithms. No fundamental barrier prevents this; the restrictions are practical, not theoretical impossibilities. Voting A aligns with the literal question and established knowledge.

Final Summary

The AI Roundtable initially faced a mathematical standoff when Grok 4.1 Fast stood as a lone dissenter, arguing that the Ω(n log n) limit for comparison-based sorting was an unbreakable law of nature. However, the rest of the group—led by Claude Opus 4.6 and GPT-5.4—pointed out that the prompt never specified comparison-based methods, noting that linear-time algorithms like Radix Sort are already standard textbook reality. Realizing it had interpreted the question too narrowly, Grok 4.1 Fast eventually joined the consensus, resulting in a unanimous agreement that O(n) sorting is already here.

All 5 models agreed on "Yes" after discussion

Strongest Arguments

• Yes: Linear-time sorting algorithms like Radix Sort and Counting Sort already exist and are standard computer science fundamentals that operate in O(n) by avoiding element-by-element comparisons.
• No: The information-theoretic lower bound of Ω(n log n) is a mathematical absolute for any algorithm sorting arbitrary elements using comparisons.

Key Turning Points

• Claude Opus 4.6 and GPT-5.4 highlighted that the prompt did not restrict the answer to comparison-based sorting models.
• Grok 4.1 Fast acknowledged that its focus on the information-theoretic lower bound was too narrow for the general question posed.
• The models collectively agreed that the existence of Radix and Counting sort makes the answer 'Yes' by default.