hn.today

I Can't Believe It Can Sort

yugen-tsuki.github.io5 points4 comments
Screenshot of I Can't Believe It Can Sort

“I Can’t Believe It Can Sort” presents a deliberately simple sorting method whose pseudocode seems too crude to work: two nested loops examine every pair of array positions, swapping their values whenever the first is smaller than the second. Despite the unusual repeated comparisons, the method arranges the values in ascending order after the loops finish. Its name reflects the surprise of seeing such a basic procedure successfully sort data. The pseudocode is credited to Stanley P. Y. Fung’s research paper, “Is this the simplest (and most surprising) sorting algorithm ever?”

The explanation gives the algorithm’s running time as O(n²), since it performs two passes over the array through nested loops. It is therefore much less efficient than familiar alternatives such as quicksort and mergesort, especially for large inputs. A Java example applies the same comparisons and swaps to an integer array, then prints the resulting values. The example illustrates the algorithm rather than suggesting it as a practical replacement for optimized sorting methods: its interest lies in the surprising fact that a simple all-pairs exchange process works, not in speed or sophistication.

Read on yugen-tsuki.github.io4 comments on Hacker News

Summary generated by AI from the linked article. hn.today is not affiliated with Hacker News or Y Combinator.

More in Programming

Aristotle Expands into Rust

Aristotle Expands into Rust

Aristotle has expanded its formal verification platform to Rust, allowing developers to prove code meets specifications and contains no undefined behavior, including in unsafe blocks. It can also verify that Rust rewrites behave like their original C code, targeting critical software such as smart contracts and infrastructure. (harmonic.fun)

The daily digest

Today's best Hacker News stories, summarized and screenshotted, one email a day.