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

21–30 of 84 posts

Re: Sorting algorithms that don’t hate you

#21

Post by bee_rider »

dataflow wrote: post #16
bee_rider wrote: post #14

Earlier quoted context omitted.

In the rare event that you have to sort a big stack of paper, merge sort is also super intuitive and easy to apply by hand.

I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.

What I’ve done is: Grading data structures exams (appropriately enough), I’d grab a handful of them, and grade them, and then sort the little stack. Then I’d put it aside to deal with later.

Eventually I realized I was running out of desk space, so I started merging little stacks of around equal size.

So the base case wasn’t 1 element, but that’s conventional for actual implementations. And the splitting wasn’t quite recursive I guess. But partial credit at least.

Re: Sorting algorithms that don’t hate you

#22

Post by dataflow »

derefr wrote: post #20
dataflow wrote: post #16

Earlier quoted context omitted.

I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.

I think most people would shortcut the "recursive task-spawning" part by just taking all the pages and spreading them out individually side-by-side on a work surface.

That's why I said it's like the iterative version of mergesort, which goes bottom-up. People don't divide things in half like in traditional recursive mergesort, is what I was saying.

Re: Sorting algorithms that don’t hate you

#23

Post by mxkopy »

hypertele-Xii wrote: post #13
chrchang523 wrote: post #8

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 differen…

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

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.

Re: Sorting algorithms that don’t hate you

#24

Post by ErikCorry »

otherfiftycents wrote: post #12
ErikCorry wrote: post #2

I had way too much fun making these animations.

What software did you use to make these animations?

I hacked it up in Toit :-)

Not the prettiest code, but it's in the examples directory at https://github.com/toitware/toit-png-display if anyone cares.

Re: Sorting algorithms that don’t hate you

#25

Post by ErikCorry »

loeg wrote: post #19
wging wrote: post #7

> Recently, Timsort has become popular, also a variation of Merge Sort. However, Timsort was not invented yet in 2008. Timsort is from 2002. Not sure where this comes from. Perhaps it wasn't as popular or widely known in 2008 as it is now, but I actually learned about it at about that time. See also: https://mail.python.org/pipermail/python-dev/2002-July/02683... (edit: timsort was introduced to Java in 2009, per htt…

I used Timsort in a class around 2010 and it had been in Python for “a long time” at that point. I also tripped on this article’s claim that it didn’t exist yet in 2008.

TIL.

Re: Sorting algorithms that don’t hate you

#26

Post by ErikCorry »

hypertele-Xii wrote: post #13
chrchang523 wrote: post #8

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 differen…

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

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

Re: Sorting algorithms that don’t hate you

#27

Post by ErikCorry »

olliej wrote: post #6

I am curious about exactly what v8 was doing at the time, because "just use Quicksort" doesn't work for inconsistent comparison functions or mutating data. These issues aren't magically resolved with "use a stable sort", but it means you're not just calling qsort(...) to perform the sort. I vaguely recall JSC actually having a literal tree sort at one point to deal with this.

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.

Re: Sorting algorithms that don’t hate you

#28

Post by lucumo »

hypertele-Xii wrote: post #13
chrchang523 wrote: post #8

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 differen…

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

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.

Re: Sorting algorithms that don’t hate you

#29

Post by CipherThrowaway »

hypertele-Xii wrote: post #13
chrchang523 wrote: post #8

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 differen…

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

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.

Post reply on HN