3 ms·
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.
by bee_rider 4y ago
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.
- dataflow 4y agoI 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 agoI 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 agoThat'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 agoWhat 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 agoBecause without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
- bee_rider 4y agoHey 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 agoOnly 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 agoI guess such a stack would fall over quickly, resulting in a heap. But again not the programming one.
- adrianmonk 4y agoIronically, the answer isn't a stack.
- dhosek 4y agoWhen I taught, I would sort graded papers/tests using quick sort. Put all the a–l in on pile and m–z in the other, then do each pile into halves and manually sort the quarters. And since I knew what the sorted set looked like, finding pívot points was trivial.
- HelloNurse 4y agoMerging stacks of papers by hand isn't the same as exchange-based computer mergesort: if the cost of inspecting and comparing items is negligible relative to actually moving them the basic, unit cost operation is splitting a sequence into three possibly empty sequences and splicing the middle piece into an arbitrary position in another sequence. In some cases reversing the spliced sequence is free ("pancake" sorting). This cost model is an important reason to merge bottom up, from sorted subsequences, without arbitrary splitting that can add work but not reduce it.
- somat 4y agoAt one point I used to work at a place that had a production process that used several hundred ibm 3480(if I remember correctly) tape cartridges. I would do a LSB radix sort afterwards to get them back in order. I think back on it with a certain amount of nostalgia now, but it was a stupid way to do operations, even at the time, They had invested big in computers in the 70's and were still maintaining the same tech stack in the early 00's when I worked there.