Hacker News Reader

Comment by chrchang523 | Hacker News Reader

Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks each element’s original position, and when two elements otherwise compare equal, use the original position as the final tiebreaker.

(With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the difference is.)

View on HN

Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.

That's my usual approach, but there are clearly some programmers who don't want to always do this, and sometimes a stable-sort library function does in fact allow them to be more productive.

This seems basically equivalent to saying that whether or not a sort is stable is irrelevant, right? If the position of elements with equal keys doesn’t matter for your application, then of course there’s no reason to use a stable sort (or convert a non-stable one to stable by whatever trick).

I'd assume cache locality makes it worthwhile, especially if the keys are big, point to big things that need to move, or live on separate drives. To that last point I'd wager stable algorithms can imply parallelization.

Well these are the sorts of arguments I made on the V8 bug, and people were not happy.

No, there could be unsortable properties that are nonetheless different. Or the use case could really require that the original order is relevant.

But yeah, I don't usually need stability either.

Forgive me for sounding like an idiot but how can two properties be different, yet unsortable?

If you can digitize it, you can probably sort it, that's true. But the sort keys can get very artificial and weird.

Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes.

You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 10x100 pixel image. But it's not very weird to pick one either.

Next you could sort on properties of the first pixel. But those are multidimensional. Sorting by the most red first, for example, would be weird.

You could still create an ordering if you need the consistency, but it wouldn't mean anything.

If you don't sort by them, you can get images that are different in ways that aren't sorted. Stability (well, instability) becomes detectable.

If you have to use an unstable sorting algorithm you'll be stuck choosing between images jumping around or being in a certain spot because the 34th pixel on the 56th line is slightly more greenish than in the image before it. It can depend on your use case which of those is least desirable.

Having a stable sort would give you another option.

Is there such a thing as visual similarity -sort?

Asking because you're actually describing a problem I have with a data set :D

Deeper comparison doesn't solve the problem because input order is arbitrary. The order may be based on a user dragging items around in a list widget, for example.

The easiest way to transform an unstable sort into a stable sort is probably mapping input from T -> (Index, T) and including the index as a sort key.

And if they're not completely equal?

...then they sort? What am I missing?

I'll spell it out then: you don't always need to sort based on the entire object's value. Comparing the whole object can be pretty expensive when you only need to sort by one field.

And allocating O(N) extra memory isn't expensive?

Reply on news.ycombinator.com