The paper "Is this the simplest (and most surprising) sorting algorithm ever?" introduces the "Sleep Sort" algorithm, a conceptually simple, albeit impractical, sorting method. It relies on spawning a separate thread for each element to be sorted. Each thread sleeps for a duration proportional to the element's value and then outputs the element. Thus, smaller elements are outputted first, resulting in a sorted sequence. While intriguing in its simplicity, Sleep Sort's correctness depends on precise timing and suffers from significant limitations, including poor performance for large datasets, inability to handle negative or duplicate values directly, and reliance on system-specific thread scheduling. Its main contribution is as a thought-provoking curiosity rather than a practical sorting algorithm.
Karl Weierstrass’s function revolutionized mathematics by demonstrating a curve that is continuous everywhere but differentiable nowhere. This “monster” function, built from an infinite sum of cosine waves with increasingly higher frequencies and smaller amplitudes, visually appears jagged and chaotic at every scale. Its existence challenged the prevailing assumption that continuous functions were mostly smooth, with only isolated points of non-differentiability. Weierstrass's discovery exposed a deep rift between intuition and mathematical rigor, ushering in a new era of analysis focused on precise definitions and rigorous proofs, impacting fields from calculus to fractal geometry.
HN users generally express fascination with the Weierstrass function and its implications for calculus. Several comments dive into the history and significance of the function, appreciating its role in challenging intuitive notions of continuity and differentiability. Some discuss its relation to fractals and Brownian motion, while others highlight the beauty of mathematical discoveries that defy expectations. A few commenters provide additional resources, including links to visualizations and related mathematical concepts like space-filling curves. Some debate the accessibility of the original Quanta article, suggesting ways it could be more easily understood by a broader audience. A recurring theme is the wonder inspired by such counterintuitive mathematical objects.
Summary of Comments ( 77 )
https://news.ycombinator.com/item?id=43155839
Hacker News users discuss the "Mirror Sort" algorithm, expressing skepticism about its novelty and practicality. Several commenters point out prior art, referencing similar algorithms like "Odd-Even Sort" and existing work on sorting networks. There's debate about the algorithm's true complexity, with some arguing the reliance on median-finding hides significant cost. Others question the value of minimizing comparisons when other operations, like swaps or data movement, dominate the performance in real-world scenarios. The overall sentiment leans towards viewing "Mirror Sort" as an interesting theoretical exercise rather than a practical breakthrough. A few users note its potential educational value for understanding sorting network concepts.
The Hacker News post linked has a moderate number of comments discussing the "Simple Sort" algorithm presented in the linked arXiv paper. Several commenters delve into the algorithm's mechanics and its relationship to existing sorting methods.
A significant thread discusses whether "Simple Sort" is truly novel or simply a rediscovery/reframing of existing algorithms, particularly insertion sort. Some argue that despite superficial similarities, the core logic and the way elements are shifted differ, making it distinct. Others contend that it's essentially insertion sort with a slightly altered control flow, focusing on the similarity of repeatedly finding the correct position for an element and shifting subsequent elements.
Several comments analyze the algorithm's performance characteristics. Some highlight the O(n) best-case scenario when the input list is already sorted (or nearly sorted), matching insertion sort's performance in such cases. However, they acknowledge the O(n^2) average and worst-case complexity, making it less efficient than algorithms like merge sort or quicksort for large, unsorted datasets. The space complexity of O(1) (in-place sorting) is also mentioned as a positive aspect.
One commenter expresses skepticism about the paper's claim of "simplicity," arguing that the code implementation, while concise, isn't necessarily easier to understand than other basic sorting algorithms. They suggest that "simplicity" is subjective and depends on the reader's familiarity with different programming paradigms.
Another line of discussion revolves around the algorithm's suitability for specific use cases. Some suggest its potential value for situations where the data is likely to be already partially sorted or where simplicity of implementation is prioritized over performance for small datasets.
A few comments also touch upon the paper's writing style and its presentation of the algorithm. One commenter questions the authors' emphasis on its "surprising" nature, suggesting that the algorithm's properties are relatively straightforward to analyze.
Overall, the comments offer a mixed reception to the "Simple Sort" algorithm. While acknowledging its simplicity and potential niche applications, many express skepticism about its novelty and overall efficiency compared to well-established sorting algorithms. The discussion primarily revolves around comparing it to existing methods, analyzing its performance, and debating its practical significance.