Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting algorithms that don’t hate you

medium.com

Post reply on HN
Print view View original

51–60 of 84 posts

Re: Sorting algorithms that don’t hate you

#51

Post by ErikCorry »

olliej wrote: post #49
ErikCorry wrote: post #27

Earlier quoted context omitted.

If you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to terminate at all.

What are you talking about? This is in a JS engine, where by design all code is untrusted. If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.

Obviously it may never crash, and it never did, even with a bad comparison function.

But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that?

Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.

Re: Sorting algorithms that don’t hate you

#54

Post by dgacmu »

orlp wrote: post #38

At FOSDEM 2023 I will be presenting glidesort in the Rust room. It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra…

I've been interested in this since your presentation in May; any plans to release the source any time soon?

(Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)

Re: Sorting algorithms that don’t hate you

#55

Post by orlp »

dgacmu wrote: post #54
orlp wrote: post #38

At FOSDEM 2023 I will be presenting glidesort in the Rust room. It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra…

I've been interested in this since your presentation in May; any plans to release the source any time soon? (Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)

Hey, the open source release will coincide with the FOSDEM presentation, so in a little under three weeks it will be under my Github account github.com/orlp.

Re: Sorting algorithms that don’t hate you

#57

Post by sorokod »

ilyt wrote: post #56

Aside from some test code being sometimes annoying why people care ? I'd be perfectly fine with just having to call StableSort vs Sort once in blue moon when I need it

Non stable sorts are very annoying and confusing in UI. I'd argue that in most cases you'd want a stable one.

Re: Sorting algorithms that don’t hate you

#58

Post by ilyt »

sorokod wrote: post #57
ilyt wrote: post #56

Aside from some test code being sometimes annoying why people care ? I'd be perfectly fine with just having to call StableSort vs Sort once in blue moon when I need it

Non stable sorts are very annoying and confusing in UI. I'd argue that in most cases you'd want a stable one.

Right, which is why I said it's fine as long as there is stable option, but I don't write UIs

Re: Sorting algorithms that don’t hate you

#59

Post by thomasmg »

graycat wrote: post #42

Let n be a non-negative integer. A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order. Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is…

I wonder which type of Shell sort you were looking at. In my experience, it is fairly simple to implement gap sequence that is faster than O(n^2). Sure it is not a stable sort. But it is really simple (a few lines of code), doesn't use recursion, and is fairly fast. In fact, I'm not aware of an algorithm that is as simple as Shell sort, and at the same time much faster than O(n^2).

Re: Sorting algorithms that don’t hate you

#60

Post by xpe »

The code examples are written in Toit:

https://toitlang.org/

> Toit is a modern high-level language designed specifically for microcontrollers

> Toit is optimised for live reloading on your microcontroller. Your code runs incrementally as you write it and you get instant feedback. Push changes over your local WiFi in two seconds and reserve your USB cable for charging your phone. You iterate quickly, learn fast, and build better things.

Post reply on HN