Hacker News Reader

Comment by Something1234 | Hacker News Reader

I'm confused, so the comparison function can modify the list? I thought most sorting algorithms assumed the contents of the list was constant. Why would I want my comparator to ever modify the list under sort?

View on HN

If you examine the modification more closely, it is just finding the list that would exhibit worst case performance - once created, that list would always exhibit the worst case as a constant list.

Once you have the resulting list, the indices are sorted, then assigning each num_solid value to that index would result in the list being constant, and then could be sorted to give such worst case behavior.

I wish the article was more clear on this.

You don't, it's just not disallowed :)

"because it prevents the user from writing a comparison function that modifies the list while sorting" is not a reason I would expect to prefer rust, and yet here we are.

It's possible in Rust too, but only for a subset of element types: those that support shared mutation (also known as "internal mutation"). For example, a type containing an `AtomicU32` or a `Mutex<T>` or a `Cell<T>` could have an `Ord::cmp` implementation that alters its value, and the compiler will not prevent this.

Yes, I had a nasty bug in an initial version of glidesort where I (naively) assumed that I could create a temporary copy of an element by doing a memcpy and call the comparison function on this temporary copy a bunch of times before throwing it away, since I assumed the comparison function would not mutate the copy. Unfortunately interior mutability means this would lead to potential double drops, and it was just not sound.

The comparison operator is not actually mutating the list, which would not be allowed in C++ either. Instead it is dynamically generating the < comparison operator for the elements in the list based on the order for which elements it is evaluated. The order for two elements remains fixed once examined and in the end it always ends up with a valid totally ordered comparison operator. The only thing required for this to work is that the comparison operator can have mutable state and that the same shared state is used for all comparisons in the sorting algorithm (asided from thread-safety so you'd need adjustments for a parallel sort).

Technically the list is not being modified but the comparison operator is dynamically determining the order of elements when the sorting algorithm checks them. This is done in a way so that the order of pairs that have already been checked previously remains fixed and it results in a valid totally ordered comparison operator in the end - but the order it ends up with depends on the sorting algorithm.

An "accessed at" field is a trivial use case.

Reply on news.ycombinator.com