5 ms·

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 div

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.

derefr 4y ago
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.
- dataflow 4y ago
  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.
bee_rider 4y ago
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.
makeset 4y ago
Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
- bee_rider 4y ago
  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.
  - adwn 4y ago
    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.
    - bee_rider 4y ago
      I guess such a stack would fall over quickly, resulting in a heap. But again not the programming one.
  - adrianmonk 4y ago
    Ironically, the answer isn't a stack.

derefr 4y ago

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.

dataflow 4y ago
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.

bee_rider 4y ago

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.

makeset 4y ago

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

bee_rider 4y ago
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.
- adwn 4y ago
  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.
  - bee_rider 4y ago
    I guess such a stack would fall over quickly, resulting in a heap. But again not the programming one.
- adrianmonk 4y ago
  Ironically, the answer isn't a stack.