Hacker News Reader

Comment by dataflow | Hacker News Reader

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.

View on HN

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.

Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.

Hey wait, good point, what the heck kind of data structure even is a stack of papers? You can insert like a linked list but hop around like an array.

Only for reasonably small stacks. Insertions at random indices won't stay O(1) when you're dealing with 100k pages and more – i.e., when you can't pick them up in one movement.

I guess such a stack would fall over quickly, resulting in a heap. But again not the programming one.

Ironically, the answer isn't a stack.

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.

Reply on news.ycombinator.com