28 ms·

Is this the simplest (and most surprising) sorting algorithm?

• fbn79 5y ago
  Is it exchange sort? https://mathbits.com/MathBits/CompSci/Arrays/Exchange.htm https://mathbits.com/MathBits/CompSci/Arrays/Exchange.htm
  • pents90 5y ago
    It’s not. The inner loop operates only from i+1 to n in exchange sort and the resulting swaps are very different.
• Ericson2314 5y ago
  This is a great example of why state is so hard. The algorithm is so simple is could easily come out of program designed to spit out all toy Algol programs, and yet what it does very unclear.
  • jonsen 5y ago
    It's only unclear if you are unable to disregard your preconceptions and simply read and understand this simple algorithm.
• _448 5y ago
  Since when have academic/research paper titles become click-baity? :)
• ansaso 5y ago
  Is this a discovery!? I'm 100% sure I wrote when I first started programming and obsessively tried to get the shortest solutions on codewars.
  • stagger87 5y ago
    Did someone refer to it as a discovery? In fact, from the introduction in the article. > It is difficult to imagine that this algorithm was not discovered before, but we are unable to find any references to it.
    • NoGravitas 5y ago
      I expect it's "commonly rediscovered because it's so simple; rarely published because it's so obviously bad".
• paulcnichols 5y ago
  A+ click bait paper title.
• trungdq88 5y ago
  Hmm, I was taught this is the “lazy” variation of bubble sort with a lot of unnecessary comparisons.
  • Dylan16807 5y ago
    Are you sure? With two separately incrementing indexes? Lazy bubble sort would still have a double loop counting to n, but it should be comparing A[j] and A[j+1]. 'i' would not be used inside the loop.
• deleted 5y ago
  [deleted]
• apricot 5y ago
  Holy shit. I independently invented... well, not quite "invented", more like "stumbled into" this algorithm when I was in elementary school learning Applesoft BASIC, and wanted to sort an array of numbers. I had no clue how to do it and just intuited there had to be two loops, one inside the other. I got the comparison wrong, saw that it sorted backwards, and just changed > to < without asking myself why it worked.
• mirrorlake 5y ago
  For me, this is a lesson in the power of semantics. If one re-writes the if statement and switches the order, if A[j] > A[i] then I find the correctness of the algorithm to be significantly more obvious. It is true that i >= j, and sorted ascending values will have the property A[i] >= A[j]. It follows that swapping happens when the values are out of order, when A[j] > A[i]
• gus_massa 5y ago
  I think I saw something similar many years ago in a side competition of the national Math Olympiad were you can use computers. [spoiler alert] IIRC one student used a weird sorting algorithm, and after looking at it for a long time and testing, we called it a very inefficient insertion sort, and IIRC it was in the "wrong" direction. So my guess is that the student used this algorithm or something very similar.
  • userbinator 5y ago
    Likewise, I also think this algorithm has been "discovered" many times but those who did were probably not intending to.
• theli0nheart 5y ago
  Does it bother anyone else that the paper has a single author and yet throughout they refer to themselves as “we”?
  • tobr 5y ago
    Just speaking for ourselves, it doesn’t bother us.
  • dimitrios1 5y ago
    They likely had at least one research assistant, proofreaders, etc. Maybe the author is attempting to distribute credit and lead the reader to infer there was just more than one person involved.
    • klyrs 5y ago
      No. Many scientific papers are written in third person. "We" actually means "me or us the author(s) and you the reader who is following along and checking these details"
      • dimitrios1 5y ago
        Or, yes. I worked as a research assistant gathering data for a professor at University who wrote 100s of papers in the area of graphics and computer vision.
      • deleted 5y ago
        [deleted]
  • Foxboron 5y ago
    It's intentional and normal. Academic papers traditionally write in plural form (regardless of co-authors) as it feels more inclusive towards the reader.
  • crote 5y ago
    The author neglected to mentioned F. D. C. Willard as co-author, obviously.
• maltalex 5y ago
  tl;dr the algorithm (the array is 1-based): for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j]
  • smusamashah 5y ago
    This is how it looks like https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... It behaves more like insertion sort.
    • chubot 5y ago
      Wow this page is very cool! I recommend clicking these four boxes: - quick sort - merge sort - custom sort (this naive algorithm) - bubble sort Then click “start”. And then you can clearly see the difference side by side, including the speed of the sort! Quick sort is quick! Merge sort is better in the worst case but slower on this random data.
      • smusamashah 5y ago
        What you are seeing isn't speed but the iterations. If you see the source, I am drawing at certain location in the loop. Sometimes when swap happens, sometimes afterwards. More than speed you are seeing the steps.
        • chubot 5y ago
          I think that is what I mean -- when there are fewer steps in the sort, then the visualization completes faster. So if you visualize two sorts side by side, it's obvious which ones completes faster, and that corresponds to the algorithm's speed, right?
          • smusamashah 5y ago
• willvarfar 5y ago
  It has a perverse beauty and will stick in my mind for a while :)
• ormei88 5y ago
  isn't that bubble sort?
  • notriddle 5y ago
    Not really. Bubble sort compares adjacent elements, while this compares every element with every other.
  • JohnHaugeland 5y ago
    Yes. Bubble sort is the comparison of every pair. If you compare only adjacent pairs, you eliminate an enormous number of redundant comparisons. This is bubble sort without the redundancy elimination. It's just that the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm.
    • recursive 5y ago
      Bubble sort will not make any changes to a sorted array. It's a similar number of comparisons. They're just different ones.
      • JohnHaugeland 5y ago
        It's a radically different number of comparisons Bubble sort scans the full array repeatedly until finished, but only along the pairwise edge, and usually finishes way early So in an array of 20 elements you have a maximum of 380 comparisons This searches Euler's Little Triangle the whole way every time, so in an array of 20 elements, you have a maximum of 380 comparisons again Seems similar, right? Except doing pairwise you're likely to exit without doing all 19 scans - at the logarithm if it's well distributed - so it probably does either 4 or 5 scans, saving ~80% of the work The issue isn't the ceiling; it's the common floor Doing it the seemingly-normal way radically changes the common floor
        • recursive 5y ago
          Thank you for making my point. So not only does this do different comparisons, it "radically" changes the number of "common floor" work. And by the way, there's something wrong with your analysis of the number of scans needed for the 20 element bubble sort. I don't understand your argument, but I did some experiments with a randomly distributed array. I never saw it sort in fewer than 12 scans, after a few dozen trials.
• shultays 5y ago
  Imo does not approach the simplicity of sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort Also I am pretty sure I saw this algorithm before. Doesn't it have a name?
  • notriddle 5y ago
    Sleep sort is heap sort. The heap is just built into your OS.
    • lmilcin 5y ago
      Sleep sort is meant as a joke. Obviously, everybody understands there exists no O(1) GP sorting algorithm.
      • falcor84 5y ago
        Assuming GP means General Purpose, yes, everyone who took an intro to algorithms should know that no sorting algorithm that relies on comparisons can do better than O(n*log(n)). But non-comparison algorithms [0] like radix sort [1] that rely on simplifying assumptions are not a joke and can be used in practice in many real-world cases. [0] https://en.wikipedia.org/wiki/Sorting_algorithm#Non-comparison_sorts https://en.wikipedia.org/wiki/Sorting_algorithm#Non-comparis... [1] https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort
        • lmilcin 5y ago
          That is why I specified "General Purpose". The moment you know something more about the data there might exist an opportunity to exploit that information to improve the algorithm. Which is an interesting topic in itself. Many times I have met people who said with absolute authority "no, it is not possible to implement this" only to be confronted with a counterexample. And that is because real life is rarely about spherical cows in vacuum. I have once implemented a transactional, log-based database for credit card terminal (20MHz ARM, 2MB total unified memory). The read (get value for key) operation was O(n^3) which the reviewers decided is "ABSOLUTELY FUCKING UNACCEPTABLE" (their words). The fun started when I asked them to suggest better implementation. They could not come up with anything even remotely as fast. And the basic reason was that n was guaranteed to be small as there wasn't even much space on the device for any more data. Other than that it exploited fantastic read ahead capability of the device plus it was so simple (basically couple nested loops) that CPU cache could be used very effectively. I remember their O(nlog(n)) was never faster and actually about 50 times slower in most operations.
• jimmyed 5y ago
  Why does the paper have the title of a clickbaitey BuzzFeed article?
  • revolvingocelot 5y ago
    So that those familiar with Betteridge's Law can just browse right on by
    • bertman 5y ago
      Having read the paper, Betteridge may actually not be true here :D
  • earthscienceman 5y ago
    This is getting more and more common in science, as a researcher's reputation and funding is more and more connected to their ability to get media/internet attention.
    • Y_Y 5y ago
      This comment made me weep internally. It's soul-crushing how relentless self-promotion is now as necessary good science for a "successful" academic career. (We can define that as getting paid anything at all by a university.) I never really had the intellectual talent or salesmanship for that, my gripe is that academia has this unsettling undercurrent of boasting and bluffing and backstabbing and it makes it just an unpleasant community in which to forge a livelihood. Surely a healthy measure of these things has always existed, but the incentives has become perversely perverse and it really drives away people with a genuine aptitude and interest from areas where they can make genuine discoveries about nature and contribute to the sum of human knowledge. And it drove me away too.
      • EVa5I7bHFq9mnYK 5y ago
        It always was this way. Source - PhD in physics, 1988.
      • 5y ago
• jakub_g 5y ago
  HTML version of the PDF: https://www.arxiv-vanity.com/papers/2110.01111/ https://www.arxiv-vanity.com/papers/2110.01111/
• meesg 5y ago
  Selection sort with extra swaps
  • jonsen 5y ago
    Insertion sort with unnecessary comparisons.
• deleted 5y ago
  [deleted]
• Apocryphon 5y ago
  Watch out, whiteboarding interviews.
• phaedrus 5y ago
  I turned in a similar algorithm for a college homework assignment, as a practical joke. (I'd been programming for 10 years already before I was able to go to college, so I was extremely bored in my first year Computer Science classes.) I'm pretty sure I used the double-loop technique to drive it, but mine wasn't quite as simple because I layered the joke by also using multiple XOR, instead of swap, to propagate the values through the array.
• Xophmeister 5y ago
  This weirdly/coincidentally [delete as appropriate] showed up as a StackOverflow "Hot" question today https://stackoverflow.com/questions/69437526/what-is-this-odd-sorting-algorithm https://stackoverflow.com/questions/69437526/what-is-this-od...
  • jonsen 5y ago
    The graphics in the first answer gives a nice demonstration.
  • bo1024 5y ago
    Yes, and the paper makes no mention of it, hm. Sorry to be a grumpy gatekeeper, but this really belongs as a blog post, not an arxiv paper, unless it were to cite more sources at least.
    • robotresearcher 5y ago
      It now serves as a reference for this algorithm, something that was missing before and not well served by a blog post. It does not claim to have invented the algorithm.
  • dtjc 5y ago
    I'd say both weird and coincidental :-). I'm the author of that StackOverflow question and have nothing to do with that paper. As far as I understand arXiv (I'm not familiar with it), the paper was submitted to arXiv before the StackOverflow answer that inspired my question, and published by arXiv after my StackOverflow question: https://arxiv.org/list/cs.DS/recent https://arxiv.org/list/cs.DS/recent
• SamBam 5y ago
  From the paper: > There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n²) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.
  • dhruvdh 5y ago
    Well, I teach Algorithms, I think there is an obvious intuition as to why this works and I use this algorithm to introduce sorting.
    • ColinWright 5y ago
      Do you really use this algorithm? Look more closely, if compares every element against every other element, and the comparison appears to be in the wrong order. This is not the Bubble Sort[0] as defined in Wikipedia. For one thing, it always has n^2 comparisons, is not always comparing adjacent elements, and does not terminate early. [0] There are some who disagree and claim that it is.
      • dhruvdh 5y ago
        Yes. I can read. It finds the largest number and places it at `i`. In the next iteration the largest number from 0 to `i` is placed at `i+1` Right up until `j` reaches `i`. Leaving a trail of orderliness. As the value of `i` increases we approach and eventually equal ascending order. What’s non-intuitive or what makes the comparison in the wrong order? It’s much easier to explain if we just stop `j` at `i` each time.
        • ColinWright 5y ago
          > Yes. I can read. I apologise. Multiple comments elsewhere have been made by people who initially thought it was a Bubble Sort, and every other course and tutorial I know of starts with the Bubble Sort. So I admit to being surprised that you use this to teach algorithms. Personally, I find the algorithm given here completely unobvious, but perhaps that's just because I derived the Bubble Sort for myself back in the mid 70s, then read about O(n.log n) algorithms, and was hooked. For me, this algorithm is very misleading, but if you find it a useful teaching tool then I've learned something, and I find it intriguing. I'd be interested to know if it's used in any other courses. Do you know of any? snip description > What’s non-intuitive or what makes the comparison in the wrong order? It works, so obviously the comparison is right. But compare it with a classical Bubble Sort: procedure bubbleSort( A : list of sortable items ) n := length(A) repeat swapped := false for i := 1 to n-1 inclusive do /* if these are out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap(A[i-1], A[i]) swapped := true end if end for until not swapped end procedure It's looking to see if A[i-1] > A[i], because then they are the wrong way round. Compare that with the code in this submission: if A[i] < A[j] then ... It's the other direction, which pulls me up short. And it's comparing every place with every other place, whereas Bubble Sort only ever compares adjacent items. Being as familiar as I am with sorting algorithms in general, this, to me, feels unintuitive. I guess my intuition doesn't match yours.
• smusamashah 5y ago
  It behaves more like insertion sort https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...
• GistNoesis 5y ago
  I remember asking the question on a stack-overflow site in 2015. https://cs.stackexchange.com/questions/45348/why-does-this-sort-algorithm-work https://cs.stackexchange.com/questions/45348/why-does-this-s... And it was answered successfully by pointing the same invariant they point in the paper. I remember finding this program through via automatic program search, so the algorithm and the question of why it works as probably been discovered many times. If only we had something that would allow to surface information from the vast amount of data available...
  • Cryptonic 5y ago
    Maybe there gotta be a paper or it does not exist xD
  • jvanderbot 5y ago
    Write it down or it didn't happen. More directly, write down the result separate from the method or it won't be discovered by the right audience.
  • somenewaccount1 5y ago
    Yes, but you asked a computer science question with computer code instead of "pseudo code and arguments of correctness.", as Rafael kindly reminded you. :)
    • civilized 5y ago
      That comment was a bit of an eye-roller. The post is perfectly clear as it stands.
      • liversage 5y ago
        The original question contained a sizeable chunk of what looks like C#. It was then edited and made much clearer perhaps in a response to the comment.
      • svat 5y ago
        See the edit: https://cs.stackexchange.com/review/suggested-edits/26152 https://cs.stackexchange.com/review/suggested-edits/26152
• mannykannot 5y ago
  Is this the simplest sorting algorithm ever? Quite possibly, but the paper is seven pages long!
  • troymc 5y ago
    A simpler sorting algorithm might be: until sorted(A) {assign a random order to the elements of A} There are n! ways to assign indices to the n items, so the expected time for the algorithm to complete grows at least as fast as n!, i.e. not ideal.
    • NoGravitas 5y ago
      This is commonly referred to as "bogosort", the archetype of the perversely bad algorithm.
    • iainmerrick 5y ago
      Is that really simpler? Both “until sorted” and “assign a random order” look significantly more complex than this entire algorithm.
• SkeuomorphicBee 5y ago
  Is this really a new algorithm? I'm fairly sure my "Algorithms" professor* taught us this sorting algorithm twenty years ago. To be fair I don't think it was taught as a serious contender, not something to be implemented in production in the future, but instead as the baseline to measure the other algorithms, and also as teaching tool to introduce the fact that computers can't "instinctively look over" the whole set (like a human sorting a small set would do) but instead have to purposefully compare everything to everything. *: (or maybe it was my "Data Structures" professor, I don't remember which of those basic courses covered the basics of sorting algorithms)
  • chmod775 5y ago
    Pretty much everything you, I, or someone else is likely to come up with, someone else will have thought of before. That's why we usually attribute inventions and discoveries to the first people to bring to market or publish. Given the simplicity of this, obviously other people have found this algorithm before. But this might be the first publication mentioning it.
    • andi999 5y ago
      The 'that's why..' part seems non sequitor to me.
  • BoiledCabbage 5y ago
    I obviously wasn't in your class, but what your describing sounds more like the role 'bubble sort' plays in comp sci education. And while this looks similar to bubble sort it is very different in behavior.
    • SkeuomorphicBee 5y ago
      I distinctively remember that bubble sort was presented later. We started with this naive double loop (and the naive simple sort as a sort into a different copy alternative) and incrementally added optimisations to reach the various named algorithms
  • 5y ago
• victorbstan 5y ago
  "It is difficult to imagine that this algorithm was not discovered before, but we are unable to find any references to it." -- I've always maintained that for academics, if somebody hasn't written a paper for it, it doesn't exist. I can say I've seen this in actual code, in the wild, and I'm sure many others have.
  • professoretc 5y ago
    It's more like, if it you can't find it, it doesn't exist. Seeing something published is probably the most common way for academics to "find" something, but if this algorithm was present in a lot of different code bases, made its way into the Linux kernel, etc., that would have been good enough, too.
• dilap 5y ago
  High level description of why it sorts: The inner loop takes an array and an index i in the array, and rearranges the array to put the largest value at index i. This is done in such a way that if the sub-array up to but not including i is sorted, then afterwords the sort will be extended such that the sub-array up to and including i will be sorted. The outer loop says, just call in to the inner loop with i from 1 to n. This will result in a sorted array, because the initial array of a single element is trivially sorted, and then we'll have by the sort-extension property of the inner loop that the progressively larger sub-arrays of 2, 3, ... up to N elements become sorted. You can see that the inner loop has the sort extension property by thinking about two cases. Case 1: If the i-th element is already larger than all previous elements, it won't touch any of the elements before i, and will only potentially make the i-th element bigger, thus clearly extending the sort though the i-th element. Case 2: If the i-th element is smaller than one of the previous elements, it won't touch any elements until reaching that smaller element; then it will start a series of swaps until it reaches index i, at which point the the original value of the i-th elment is left inserted in sorted position into the sub-array up to and including i. So at this moment we have the sort extension property. From there, it may increase the value of the i-th element and change later elements, but of both those will preserve the sub-array sort.
  • dvogel 5y ago
    It is being likened to bubblesort in various places but your description (which I quite like) makes it seem like quicksort with an intentionally bad (worst possible?) bifurcation.
    • dilap 5y ago
      Well, it's not really dividing, sorting, and merging, so I wouldn't say it's too similar to quicksort. It's basically insertion sort, but with the curious property that the last value of the sorted subarray immediately and always has the correct value, and we then "gently" insert new values into the sorted subarray. smusamashah linked to a nice sort visualization. https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... Tap the "Insertion Sort" checkbox on the right, and then the "Start" button below that. You can see how both sorts are slowly constructing a sorted subarray, but this sort has the interesting property that the tail of the sorted subarray immediately obtains its maximum brightness, and new values are gently incorporated into the array, while the insertion sort tail is just the brightest value encountered so far, and the latest value is "abrutly" sifted down into its appropriate place. It feels like this sort might minimize some kind of "sort entropy" metric? I.e., visually it looks very smooth. Each step along the way to sorted is very small.
• egberts1 5y ago
  I recall some kind of sort that requires a construction of link list for storing index numbers of the original array. Only that the final link list (of index numbers) were in sorted order of which you then summarily write in the final array. Which would have consumed some (n*(row-size)+n*(link-ptr-size+value-size) memory outside of its original array. probably did O(n^1.5 for read operation which is WAY better than O(n^2) for bubble-sort. Best in-its class algorithm for swap at O(2), worst case? Delving into swap breakdown, its write operation might be O(3n+1) for writing a value then updating a link list pointer for each entry and for its link value into that final array; +1 for that NULL pointer at the end. was arguably the lowest O (way back then) but at extremely high cost of memory. Never did learn which sort class did that variant falls into. EDITED: insertion class, memory-hog-style.
  • egberts1 5y ago
    Now I remember, it was a college try to improve the read operation of insertion-class sort algorithm. One guy knocked down the time order considerably by doing tiny pre-bubblesort in blocks before entering into the link-insertion thereby making less passes over its million link-list chains: but only because he leveraged to fitting within its CPU L2/L3 cache. Professor said that the order got worse but not by huge logarithmic scale despite time speed-ups for completion. Dang, the O order just got complicated for multi-level caches.
• bingohbangoh 5y ago
  Not entirely unrelated, learning how merge sort worked and why it was more efficient than the naieve first guess of insertion sort was the light bulb moment in my understanding of computer science.
• gotostatement 5y ago
  so now academic papers are titled like clickbait? xD
• svat 5y ago
  [Edit: I took a quick glance at the paper and got carried away; the rest of this comment is about a different algorithm apparently known as "exchange sort", and an interesting property of it. The algorithm in the paper is actually different, and indeed more surprising.] Hey! That's my sorting algorithm! (Well, I'm sure it has been independently discovered many times, but one of those times was by me before I had learned of O(n log n) sorting; I used it many times including in the INOI 2004 programming contest, about which I asked the following question ten years ago in 2011 on math.SE about this algorithm and Catalan numbers, a truly surprising property that is not mentioned in this paper: https://math.stackexchange.com/questions/36022/how-do-the-catalan-numbers-turn-up-here https://math.stackexchange.com/questions/36022/how-do-the-ca... > For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following: //Given array a[1], ... a[n] for i = 1 to n: for j = i+1 to n: if a[i] > a[j]: swap(a[i],a[j]) > It looks like bubble sort, but is closer to selection sort. It is easy to see why it works: in each iteration of the outer loop, `a[i]` is set to be the smallest element of `a[i…n]`. ---- Also: A few years ago I emailed Prof. Richard Stanley of Enumerative Combinatorics fame asking whether it was related to any of the hundreds of problems in his Catalan Numbers list, and he said he didn't know a direct connection at the time (so maybe it's an addition to his list?): > > permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left] > Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423. > Non-example: The permutation 3412 has four inversions (13), (14), (23) and (24), and the product (24)(23)(14)(13) is 4321 which is not the same as 3412. > Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples). And 14 is C_4, the fourth Catalan number.
  • buzzin_ 5y ago
    What do you mean, it looks like bubble sort? It is bubble sort.
    • svat 5y ago
      Bubble sort only swaps adjacent elements. The one I used is a lesser-known sort apparently called "exchange sort".
• daneel_w 5y ago
  Looks just like a slightly smarter insertion sorter, which is a slightly smarter exchange sorter, which is a slightly smarter bubble sorter. I don't see what's surprising about the approach.
• alex_smart 5y ago
  The amount of people in this thread that can't read an intro to a paper is too damn high.
• strangattractor 5y ago
  It is simply an inefficient bubble sort. A bubble sort makes an improvement by not comparing values that are already sorted. Eons ago this example was a common way to introduce making algorithms more efficient. Naive Implementation -> Better Implementation. // A function to implement bubble sort void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) // Last i elements are already in place for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); }
  • ColinWright 5y ago
    If you read elsewhere in this discussion you will see many people giving reasons why this is not simply an inefficient Bubble Sort. You may disagree with them, as others do, but the situation seems rather more complicated than just saying "Oh, it's just a Bubble Sort."
  • dahart 5y ago
    No. Look again. The compare is opposite of bubble sort’s.
• areyousure 5y ago
  Some links to discussions and/or accidental discoveries of this algorithm: OP (2021): https://arxiv.org/abs/2110.01111 https://arxiv.org/abs/2110.01111 Stack Overflow (2021, linked by 'Xophmeister in this discussion): https://stackoverflow.com/questions/69437526/what-is-this-odd-sorting-algorithm https://stackoverflow.com/questions/69437526/what-is-this-od... Stack Overflow (2021, linked from previous): https://stackoverflow.com/revisions/69435932/1 https://stackoverflow.com/revisions/69435932/1 Stack Overflow with 5 downvotes! (2020): https://stackoverflow.com/questions/63214115/what-is-the-name-of-this-sorting-algorithm-is-it-bubble-sort-most-easy-sorting https://stackoverflow.com/questions/63214115/what-is-the-nam... Stack Overflow (2020): https://stackoverflow.com/questions/59802669/pointer-array-sorting-in-c-has-unexpected-output https://stackoverflow.com/questions/59802669/pointer-array-s... Computer Science Stack Exchange (2015, linked by 'GistNoesis in this discussion): https://cs.stackexchange.com/questions/45348/why-does-this-sort-algorithm-work https://cs.stackexchange.com/questions/45348/why-does-this-s... Stack Overflow (2014!): https://stackoverflow.com/questions/25276619/how-should-i-analyze-and-or-prove-this-simple-sorting-algorithm https://stackoverflow.com/questions/25276619/how-should-i-an... Reddit (2014, same as previous): https://www.reddit.com/r/algorithms/comments/2dect7/how_should_this_sorting_algorithm_be_analyzed/ https://www.reddit.com/r/algorithms/comments/2dect7/how_shou...
  • svat 5y ago
    Wow how did you find all these? Have you been keeping track all these years, or did you somehow search for and find this just now?
    • areyousure 5y ago
      All today. I have been trying to carefully craft searches on Google and Stack Overflow. I wish Google Code Search were still around, or that Github code search were better.
      • password4321 5y ago
        https://sourcegraph.com/search https://sourcegraph.com/search ? I always get it confused with self-hosted https://github.com/CoatiSoftware/Sourcetrail https://github.com/CoatiSoftware/Sourcetrail but I think Sourcetrail just shut down.
• asow92 5y ago
  "ICan’tBelieveItCanSort(A[1..n])" what an incredibly cheeky academic paper.. I love it.
• limoce 5y ago
  Letme re-interpret what the i-th iteration of the algorithm does: 1. for j = 1..i-1, we're trying to "insert" a[i] into a[1..i-1]. Try simulating it yourself. I believe you will find out it's insertion sort. 2. for j = i..n, we're replacing a[i] with the smallest element among a[i..n]. Why it works: either (1) or (2) alone CAN DO THE SORTING. They do not conflict with each other. Therefore, we can "optimize" this algorithm in at least two ways. BTW, hope future powerful compilers can do this :)
  • kilovoltaire 5y ago
    I think you misread the code, the comparison is the opposite of what you might expect, so a[i] is always the largest element, and it is not inserted into a[1..i-1]
    • edflsafoiewq 5y ago
      No, GP is correct. At the beginning of an outer loop iteration, a[1..i-1] is sorted with a[i-1] the maximum element. The inner loop inserts a[i] into a[1..i-1] so that at the end of the iteration, a[1..i] is sorted with a[i] the max.
      • Jtsummers 5y ago
        No, GGP is incorrect. To be clear, they wrote: > Letme re-interpret what the i-th iteration of the algorithm does: > 1. for j = 1..i-1, we're trying to "insert" a[i] into a[1..i-1]. Try simulating it yourself. I believe you will find out it's insertion sort. > 2. for j = i..n, we're replacing a[i] with the smallest element among a[i..n]. That is, they're saying in (2) that after an iteration of the outer loop, the ith value will be the smallest of all the values that succeed it in the sequence. This is demonstrably false. It is always the maximum value of the sequence itself, regardless of its initial position relative to i. The following Python code is used to print out the result of running the inner loop on an arbitrary sequence but without altering the original value (so it won't actually be sorted at the end). The point is to demonstrate that the maximum value always ends in the ith position: def inner(a, i): for j in range(len(a)): if a[i] < a[j]: a[i], a[j] = a[j], a[i] print(a) def outer(a): for i in range(len(a)): inner(a.copy(), i) a = [5,4,3,2,1,6] outer(a) [6, 4, 3, 2, 1, 5] [4, 6, 3, 2, 1, 5] [3, 4, 6, 2, 1, 5] [2, 4, 3, 6, 1, 5] [1, 4, 3, 2, 6, 5] [5, 4, 3, 2, 1, 6] Note that 6 ends up in the ith position after finishing the inner loop. If we let it sort (so remove .copy()), after each iteration the maximum value is, again, always at the ith position: [6, 4, 3, 2, 1, 5] [4, 6, 3, 2, 1, 5] [3, 4, 6, 2, 1, 5] [2, 3, 4, 6, 1, 5] [1, 2, 3, 4, 6, 5] [1, 2, 3, 4, 5, 6] GGP is correct that it's basically insertion sort otherwise, (1). To illustrate, the behavior if you don't compare every pair is the same as insertion sort: [5, 4, 3, 2, 1, 6] [4, 5, 3, 2, 1, 6] [3, 4, 5, 2, 1, 6] [2, 3, 4, 5, 1, 6] [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] This is done by stopping the inner loop once j reaches i.
• yodelshady 5y ago
  Slightly OT, but it always slightly bugs me that sorting algorithms are taught *only* in the context of computers, which obey different physics to sorting things. Has anyone done work on sorting algorithms under different cost functions than just "minimise comparisons"? I'm thinking something like: 1. Allocation of new space is free, at least up to 2x the input size. 2. Moving a contiguous set of elements is as cheap as moving one element. 3. Moving an element, or set of elements, has a cost proportional to the distance moved.
  • gus_massa 5y ago
    Not exactly what you are asking for but ... To sort ~500 student tests by name, my favorite algorithm is * Each person grabs a bunch of test. Split the test in 4 piles, using the first letter: A-F, G-L, M-Q, R-Z The same 4 piles for everyone. (I don't remember the exact borders. It may depend on your language. Perhaps 5 piles is better.) * Each persons grabs a pile. Split each pile in subpiles by the first letter again. If some letter is too popular, split it using the second letter. * Sort each small subpile, that has only 10-20 tests, probably using insert sort. * Make a giant pile. This can be classified as a combination of radix sort and insert sort. It's easy to parallelize to 5-10 persons. If you later realize there are ~50 more test, just sort them using your favorite method and then use merge them, like in mergesort (or timsort?).
  • tgb 5y ago
    What's the optimal sorting algorithm for your Bridge hand? Sorting and holding 13 cards is tricky enough to make me wonder.
    • yodelshady 5y ago
      That's the sort of thing I hand in mind, yes. Should probably write what I think I'm doing down. Though in that specific situation, the sufficiently smart and motivated could probably infer hand information.
    • thehappypm 5y ago
      Yeah it’s a little different because the human mind isn’t procedural — you can perceive multiple cards at once, at a fuzzy resolution. You look at a hand and see “okay an ace, 3 face cards, some other cards” then scan to resolve. So an optimal algorithm needs to take that cognition into account.
• CobrastanJorji 5y ago
  This is fun but I do wish papers would stop using "obvious" or "not difficult" so frequently. This paper has five uses of "obvious," 3 uses of "clear" or "clearly," a "should not be difficult," a "what can possibly be simpler?," and a "It is difficult to imagine that this algorithm was not discovered before." Is this a particularly complex algorithm or proof? No. But it reads like the author was terrified that someone would be able to understand their paper simply by reading it once and worried that would make the author look dumb. That's backwards, though. Easy to understand concepts are a good thing.
  • tgb 5y ago
    Of the five "obvious" words, two of them are used to say that something is not obvious and your last two examples are something entirely different. The uses here seem quite reasonable. But these words should be helpful, not insulting! If it's not clear, as the author claims, then you've likely misunderstood something. No point pondering it for twenty minutes, better go back and reread the statement first. But of course they do get misused and there's not much more demoralizing than getting stuck on something 'obvious.'
  • yupper32 5y ago
    You're going about it backwards. It's not that those phrases need to be removed from this paper, it's that this paper should have been a blog post. The algorithm is not novel or in need of academic scrutiny. It's just a fun little sorting algorithm.
  • sytelus 5y ago
    Plus I completely dislike the title. These kind of papers treat arxiv as if it is discussion group. It is not. It is paper repository for things that has been written with lot of care and thought.
• amelius 5y ago
  If it contains an "if" statement then GPUs won't like it, and I wouldn't call it "simple".
• zeroimpl 5y ago
  As an algorithm, this is simple (4 very basic lines of code). As an approach to sorting, this is fairly complex - many simpler to understand solutions exist.
• deleted 5y ago
  [deleted]
• gamacodre 5y ago
  Back in the 80's and 90's, working on consoles in very tight space constraints, there were times we’d go with a horribly inefficient implementation of something like sort, because we only needed to sort 8 things and the savings in bytes of code was more important than the savings in time from a “better” algorithm. Those abominations could be tweaked throughout the development of the game, and along the way we'd sometimes "rediscover" a more common (sane) algorithm. The refinement in this paper reminded me a lot of that.
• deleted 5y ago
  [deleted]
• egwor 5y ago
  I think that they should name it Beautiful Sort
• cratermoon 5y ago
  I kind of like Sleep Sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort Seen previously on HN https://news.ycombinator.com/item?id=2657277 https://news.ycombinator.com/item?id=2657277
• worik 5y ago
  Ok, it is not bubble sort. It is worse.
• nazgulnarsil 5y ago
  I had a similar experience in college. The assignment was to print out a tree structure with any given initialization values. The professor and everyone else in the class printed the tree top down, like tree diagrams in textbooks. This required a bunch of fiddly spacing considerations. I realized that printing it out left to right required far simpler spacing. I think the final code was less than 20 lines with the core logic being 7 lines. The professor was very surprised it worked.
• jacobmischka 5y ago
  > There is nothing good about this algorithm. Seems a bit harsh.
• lacker 5y ago
  I feel like bubble sort is simpler. repeat n times: for i = 1 to n-1: if a[i] > a[i+1]: swap(a[i], a[i+1]) It's true you have to add and subtract 1, but you only have one variable, and of course the rationale for why it works is far simpler.
• fartingflamingo 5y ago
  Reminds me of the remarkably little-known AlgoRythmics sorting dances [0]. [0] https://www.youtube.com/user/AlgoRythmics/videos https://www.youtube.com/user/AlgoRythmics/videos
• beyondzero 5y ago
  This is silly but sort of relevant. During college junior year (1993) as a physics major I took a class in digital electronics (which included 68000 assembler programming). We had a lab contest to create the fastest sorting routine for a set of random unique numbers between x and y. I won the contest by setting to 0 a y-x register range of memory and then inserting each number into the range based on the number itself ("27" into register 27, "18" into register 18, etc.). Then I printed out all non-zero numbers in the range. The other 20 or so students did versions of bubble-sorting and called my solution a cheat. The professor defended my victory as I had not broken any of the rules of the contest...
  • catwell 5y ago
    This is a slightly simpler (because of unicity) version of bucket sort or counting sort.
    • sli 5y ago
      I remember seeing a (gag) variation of counting sort that just provided each element as an argument to `sleep`.
      • tylerhou 5y ago
        That’s more like heapsort, because the OS will use a heap to implement a priority queue that contains times for when the next process needs to be scheduled.
      • OldHand2018 5y ago
        Brilliant! Although if it took a long time to enumerate the list of elements…
        • ballenf 5y ago
          Pass them in as milliseconds or nanoseconds?
      • shitlord 5y ago
• grumpopotamus 5y ago
  http://wiki.c2.com/?QuantumBogoSort http://wiki.c2.com/?QuantumBogoSort QuantumBogoSort a quantum sorting algorithm which can sort any list in O(1), using the "many worlds" interpretation of quantum mechanics. It works as follows: 1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway. 2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.) 3. All remaining universes contain lists which are sorted.
  • laurent92 5y ago
    The next generation will laugh at us for our first implementations of various algorithms in quantum computers. It will look like what you describe. In fact, they’ll laugh at us for our first implementations of AI, which will look so stupid that they’ll call them BogoAI.
• tu7001 5y ago
  Lenin Sort: guaranteed linear time, if element is not sorted, get rid of it! :-D
• xtat 5y ago
  So academic papers have also gone the route of clickbait titles :)
• justicezyx 5y ago
  This is bubble sort https://en.m.wikipedia.org/wiki/Bubble_sort https://en.m.wikipedia.org/wiki/Bubble_sort This should be in the standard college level CS classes. Edit: As mentioned elsewhere, this is not exactly same as the textbook bubble sort When I wrote this, I am saying in the sense that each outer iteration "bubbles" up to its correct place, by swapping. Thinking twice this also appears to just be a selection sort, as it indeed swaps in each iteration the smallest element But overall, the algorithm is not surprising at all to me. It seems unusual indeed though.
  • ColinWright 5y ago
    I suggest you read elsewhere in this discussion, where many people have claimed it is a Bubble Sort, and most have then changed their minds. Consider, a Bubble Sort (as documented in TAoCP, for one) only ever compares elements in adjacent locations, whereas this routine compares every location to every other location.
  • jonsen 5y ago
    Then think trice. Selection sort gets its name from doing work to find, select, the overall smallest element. This algorithm just takes the element at position i and inserts it at the so far right place in the sorted subarray to the left of i. It's an inefficient (and somewhat obscure) variant of insertion sort.
    • justicezyx 5y ago
      But overall it's not surprising to me...
• lettergram 5y ago
  I've been using the same program for years (since 2015) for interviews, intentionally adding some issues and asking what the code does, how to fix the bug(s), what to name the function, what are some properties that are problematic, etc. Kind of a fun interview, but actually explores peoples knowledge.
• ernopp 5y ago
  No one repping the old drop sort. Just returns the first item of the list, which happens to be an ordered list. Simples.
• kevin_thibedeau 5y ago
  It would make for a simple hardware implementation. More general than fixed size sorting networks. It if all happens in parallel you trade gate area for speed.
• tester756 5y ago
  cosmic ray sort while (!IsSorted(array)) { }
• noobermin 5y ago
  Interesting, but I'm amused by the writing style. I'm assuming it won't be submitted to a journal because the style reads like a blogpost.
• musicale 5y ago
  Isn't this basically selection sort with extra (useless) iterations in the inner loop?
  • jonsen 5y ago
    No, it's basically insertion sort. With unnecessary comparisons yes.
• kragen 5y ago
  The algorithm from the paper is indeed an astonishingly simple sorting algorithm, and it is indeed surprising that it works: void cantbelievesort(int *p, size_t n) { int tmp; for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { if (p[i] < p[j]) tmp = p[i], p[i] = p[j], p[j] = tmp; } } } That's 10 lines of code according to David A. Wheeler's 'SLOCCount,' though arguably 9 would be fairer. Its cyclomatic complexity is 3, with a deepest statement nesting level of 4, and it has 5 variables: three locals plus two arguments. It compiles to these 17 amd64 instructions, occupying 44 bytes of code, although I could probably shave off a third of that if I wrote it by hand: 4007cc: 31 c0 xor %eax,%eax 4007ce: eb 22 jmp 4007f2 <cantbelievesort+0x26> 4007d0: 8b 0c 87 mov (%rdi,%rax,4),%ecx 4007d3: 44 8b 04 97 mov (%rdi,%rdx,4),%r8d 4007d7: 44 39 c1 cmp %r8d,%ecx 4007da: 7d 07 jge 4007e3 <cantbelievesort+0x17> 4007dc: 44 89 04 87 mov %r8d,(%rdi,%rax,4) 4007e0: 89 0c 97 mov %ecx,(%rdi,%rdx,4) 4007e3: 48 ff c2 inc %rdx 4007e6: eb 02 jmp 4007ea <cantbelievesort+0x1e> 4007e8: 31 d2 xor %edx,%edx 4007ea: 48 39 f2 cmp %rsi,%rdx 4007ed: 75 e1 jne 4007d0 <cantbelievesort+0x4> 4007ef: 48 ff c0 inc %rax 4007f2: 48 39 f0 cmp %rsi,%rax 4007f5: 75 f1 jne 4007e8 <cantbelievesort+0x1c> 4007f7: c3 retq However, arguably, this sort routine is even simpler. It may or may not be surprising that it works: void dumbsort(int *p, size_t n) { int tmp; for (size_t i = 1; i < n; i++) { if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0; } } By the same metric, that's only 8 lines of code (also only 8 by my "fairer" metric), its cyclomatic complexity is only 2, its deepest statement nesting level is only 3, and it has only 4 variables (the same two arguments, but two locals instead of three). It compiles to only 15 amd64 instructions, occupying only 43 bytes: 4007f8: b8 01 00 00 00 mov $0x1,%eax 4007fd: eb 1e jmp 40081d <dumbsort+0x25> 4007ff: 4c 8d 04 87 lea (%rdi,%rax,4),%r8 400803: 48 8d 54 87 fc lea -0x4(%rdi,%rax,4),%rdx 400808: 41 8b 08 mov (%r8),%ecx 40080b: 44 8b 0a mov (%rdx),%r9d 40080e: 44 39 c9 cmp %r9d,%ecx 400811: 7d 07 jge 40081a <dumbsort+0x22> 400813: 45 89 08 mov %r9d,(%r8) 400816: 31 c0 xor %eax,%eax 400818: 89 0a mov %ecx,(%rdx) 40081a: 48 ff c0 inc %rax 40081d: 48 39 f0 cmp %rsi,%rax 400820: 72 dd jb 4007ff <dumbsort+0x7> 400822: c3 retq On every complexity metric that was ready to hand, dumbsort is simpler than cantbelievesort. Except computational complexity: dumbsort is O(N³) while cantbelievesort is only O(N²). Dumbsort is similar to gnome sort, but arguably somewhat simpler: whenever it finds an out-of-order pair, after reversing it, it throws up its hands and starts over (i = 0, xor %eax, %eax). I don't think I invented it, but I can't remember who did. I'd be grateful for pointers.
• nibbula 5y ago
  The only thing surprising about this, is how bad many people's education is. If you don't learn a slow way to do something, how can you know if a fast way is fast? If you don't try to solve basic problems for yourself, how can you expect to solve hard problems if you get to them? Entirely self-taught people will likely have learned this. Children before the age of computers "invented" this algorithm, and many others, while sorting sticks on the beach.
  • notriddle 5y ago
    This is not selection sort. It is not insertion sort. And it is not bubble sort. Those three algorithms are sort of intuitive. This is not.
• ac42 5y ago
  I am not clear why the proof is so long. By induction, the first i elements are already smaller than the A[i], so it's essentially an unoptimised version of for i: 0..n-1 A[i] = min(A[i:n])
  • areyousure 5y ago
    After the first iteration of the loop (and every other one too), A[i] is the maximum of the array, not the minimum.
    • ac42 5y ago
      Oh crap, now I see it. Thanks!
• xwdv 5y ago
  I’m pretty sure I’ve used this algorithm in situations where I needed to quickly sort for small values of n and was too lazy to find a better way.
• forgotmypw17 5y ago
  I think bubble sort is the simplest one to understand. I still use it in a pinch, the delay is barely noticeable on today's hardware.
• scotty79 5y ago
  For the people that don't want to open PDF here's the algorithm from the paper: for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j]
  • agent5566 5y ago
    Well, many people who tried to implement the bubble sort for the first time “invented” this algo, it’s just not optimized bubble rather then insertion sort, is it worth an article?
    • ColinWright 5y ago
      If you read elsewhere in this thread you'll see that there really is enough discussion to suggest that yes, this is worth an article. And it really, really isn't Bubble Sort. One of the defining features of Bubble Sort is that it only ever compares elements in adjacent locations. Others are claiming that if you optimise this then it becomes Bubble Sort, but someone else observes that if you "optimise" differently you end up with Insertion Sort. That suggests that this is not Bubble Sort. It's something different that can be mutated into Bubble Sort, but it is, of itself, not Bubble Sort.
• jordiburgos 5y ago
  That is Bubble Sort, not surprising.
  • ColinWright 5y ago
    If you read elsewhere in the discussion you will see many people explaining why this is not a Bubble Sort. One of the defining characteristics of Bubble Sort, as defined in TAoCP and many, many other places, is that it's only ever the elements in adjacent locations that are compared.
    • jordiburgos 5y ago
      Yes, but the way to traverse the array is the same as Bubble Sort. With that so specific definitions, I could just get any other sorting algorithm and change it with different ways of comparing the elements to create "new" sorting algorithms.
      • ColinWright 5y ago
        I disagree. The second loop runs from 1 to n, whereas in Bubble Sort it runs from 1 to n-1. The comparison here is between A[i] and A[j], whereas in Bubble Sort it's always only between A[i] and A[i+1]. This one always performs n^2 comparisons, whereas Bubble Sort never performs n^2 comparisons. This one compares elements to themselves, whereas Bubble Sort never compares and element with itself. If you sort the array [1,2,3], the first thing this routine does is swap the 1 and 2, giving [2,1,3], whereas Bubble Sort runs along the array, makes no swaps, and exits. This is not Bubble Sort. It's true that if you take an existing sorting algorithm and change things around you can get other sorting algorithms. The question is then one of just how different it is. If you choose to believe this is "just Bubble Sort" then that's up to you, but I disagree.