Way OT: Day job possible math related question.

[DICKEYBIRD]

Got way behind at work and have a pile of invoices to put into numerical sequence, smallest number to largest. There's one stack about 3" thick which is already sorted and roughly 35 smaller stacks (about 3/8" thick) each having numbers that are in generally ascending order.

A co-worker is going to help today and I've been trying to come up with a better way other than just merging a few smaller stacks at a time then merging those into the big one. The final pile has to go into a storage box. Any brilliant ideas out there? The breadth of knowledge & experience here never ceases to amaze me so I thought I'd throw it out & see what happens.

Please, no discussions about why the heck I have to do this inane [email protected] at my age & experience...I feel bad enough already.

[vpt]

I wouldn't sort into smaller stacks first and then into the big stack, that seems like doing it twice.

I would just start off the top of what you have left to file and stick them one at a time into the big stack where they are supposed to go. One time and done.

[lynnl]

This is an interesting problem. Interesting ...but tedious!

Ideally you'd want to get all those small stacks into one stack sorted in the same order as your 3" stack, as starting point. But you imply that the small stacks are only "in generally ascending order" which means you may have to go thru a few iterations, or else stop and go back at times.

But to make effective use of the co-worker help, the two of you should work on getting the small stacks sorted and merged into two stacks with each covering half the range of invoice nmbrs. Then break the big stack into two smaller ones covering the same range of nmbrs., so that each of you can be simultaneously bumping/merging those smaller stacks against the two "half stacks."

[Ripthorn]

There are actually a couple of really cool mathematical tricks that come in to play here, but not sure they would really reduce the amount of time. One of them (I think, if I can remember well enough) is that if you are starting with a completely random stack of numbered items, is pick one at random. If it is out of place, put it roughly half way between where it was found and where you think it "should" belong. This process is continued (putting in the exact place when convenient) and "should" minimize the number of operations performed. Again, I could be remembering it wrong.

One caveat: because many of the smaller stacks are already mostly in order, the above wouldn't help much, other than distract you temporarily from what you are doing.

[mklotz]

In the world of computer science (spit), the study of sorting optimization is very important. There's a modest discussion at...

http://en.wikipedia.org/wiki/Sorting_algorithm

(No, I'm not related to Tiffie.)

When I studied the problem, the "quicksort" routine was best, at least for arrays about which one had no a priori information. You have some information about the array to be sorted, so that may affect the choice of an algorithm.

http://en.wikipedia.org/wiki/Quicksort

The problem is that these are all computer algorithms and the comparisons of them may not apply to sorting done by humans. Sorry, but I can't be of any help there.

[CalM]

I would start with a large cleared off table. bigger numbers go to the right and down. Make columns with the invoice numbers showing.

That's taking advantage of "Visual Basic" firmware . ;-)

[DICKEYBIRD]

You guys are the best, thanks!

Ya gotta love the sorting algorithms. The perfect HSM'r solution: Let's make a new tool to complete a job! If the job was larger, it'd possibly be worth trying to use a computer to help.

The smaller stacks were each made from a daily list of invoice numbers that came in as a .txt file so there's probably a way that a computer savvy person could delete all the unneeded info, import that data into some other program and make a rough outline of a sort process.

[TGTool]

If the job was larger, it'd possibly be worth trying to use a computer to help.

Now there's a mental picture with some humor in it. Give the computer the range of numbers. Fine. In no time it will tell you the correct order. Now all you need to do is put the physical sheets in the same order. That sounds like a computer's idea of help for humans.

[vincemulhollon]

the comparisons of them may not apply to sorting done by humans

Aim in between. I'm too young for unit record equipment although I always found it mechanically interesting and the way they sorted punch cards mechanically was a radix followed by a merge, mostly.

So you radix sort by making ten piles by sorting only the biggest digit. Then sort the pile beginning with 3 (or whatever) by the second digit making 10 more piles. Then you just kinda stack up the sorted piles. So each original pile is now in perfect order without too much trouble.

A merge sort is pretty cool, given sorted subpiles you just look at all the piles and pull the highest number you see, repeat until you run out of piles. Note that you can cascade pretty well, so you can combine 2 into 1 or 3 into 1 and then repeat until you run out of piles.

If one pile is close to being in order and only has maybe one mistake or something, you can polish the stack by reading it and kicking out everything thats out of order. If nothing gets kicked out, its in order. If something got kicked out, sort and merge it back in, a deck minus the mistakes is polished smooth and perfect so all you need to sort is whatever gets kicked out, quite possibly just one item.

In my infinite spare time I've occasionally thought of making punch card manipulation machines much as some daydream of homemade engines. I could eventually build an entire small scale version of a 1940s punch card unit record machine calculation office.

[Rosco-P]

In my infinite spare time I've occasionally thought of making punch card manipulation machines much as some daydream of homemade engines. I could eventually build an entire small scale version of a 1940s punch card unit record machine calculation office.

See: http://www.columbia.edu/cu/computinghistory/sorter.html Had some exposure to one of these in the administrative IT department of the Engineering school I worked at. Not my favorite task, I'd rather decollate a 1000 page, five part report than babysit the card sorter.

[gundog]

Not knowing just how many you have it is hard to say but I would probably get some blank pieces of papaer and fan them out label each blank sheet with a spread of 10-20 or even 100 and quickly stuff each one in that range then sort each range and stack the bunch in order when finished.

[lynnl]

If the job was larger, it'd possibly be worth trying to use a computer to help.

The smaller stacks were each made from a daily list of invoice numbers that came in as a .txt file so there's probably a way that a computer savvy person could delete all the unneeded info, import that data into some other program and make a rough outline of a sort process.

In this case, since the goal is to arrange physical pieces of paper in sorted order, a computer will be no help.
I spent the better part of 20 years writing COBOL programs which included routines to do this. Pre-written routines were available to first sort the files, and normally multiple files could be concatenated together as the input. But there were occasions when the merge process would have to be hand written.

The process is simple and straightforward once all files (here invoice stacks) are in the desired order:
1 - Read the first # (smallest or largest, depending on which way you've sorted)
2 - Put it in the output file
3 - Read next # from that stack, if it's the next sequential # put it in output pile, if not scan #(s) from other pile/stacks to find next
seq'nl # and put in file (stack)
4 - If some input stacks remain go to 3 and repeat, else finished!

[DICKEYBIRD]

Wow, very interesting info & links, thanks one & all. My Dad used to bring stacks of punch cards home for me to play with when I was about 10 yrs. old from a job he was helping a friend with. I cut 'em up & hooked them up to my bicycle rubbing on the spokes to make a racket. Not quite as noisy as real playing cards but then who was allowed to waste precious playing cards back in the frugal fifties. (Rich kids, that's who.)

Turns out the job was a no-brainer for someone who's brain is wired differently than mine. My buddy & co-worker Jeff sat down, took a look & said "Is this all we gotta do?" He spread out all the stacks, looked at the numbers, put the smaller stacks into groups based on some order knownst to him & unknownst to me, started shuffling & stuffing invoices between stacks and in less than 30 minutes was finished. Mind you, I didn't check his work though.

He's a lifelong poker player and usually does OK at it whereas when I see a deck of cards, I break out into a cold sweat remembering the trouncing I took as a younger man. Apparently his brain works differently than mine & sorting numbers is a trivial task. I guess the old "Different strokes for different folks" adage applies.

[Paul Alciatore]

I have some experience with manual sorting, as opposed to the computer sort. I would sort the 35 unsorted piles first and then merge that pile with the already sorted one.

To sort the 35 unsorted piles, I would get a table where there is room for ten piles and one of you on each side. Each of you grab a pile. Look at only the LAST number of the invoice number and sort them into the ten piles based only on that last number. Continue until all 35 piles have been done.

Then stack those piles, with the lowest number (0) on the bottom and the highest number (9) on the top. Do this in two halves, one for each of you 0-4 and 5-9. One of you take 0-4 and the other take 5-9. Now each of the ten target piles is divided into two also, 0-4 and 5-9: it is probably best to have them next to each other, down the center of the table. Look at only the tens digit (second from the right) and sort by that digit only. Notice, that as you do this, the unit digits will stay in their already sorted order with the high ones on the bottom and the lower ones on the top. When each of you has done his/her half, stack the two halves (0-4 and 5-9) in proper order. Repeat this step for all of the remaining digits until you reach the most significant digit, on the left.

Now the 35 unsorted piles are sorted. It should be a quick job to put that pile next to the already sorted ones and simply take the next number from whichever pile and put it upside down in a third one. Done.

It sounds a bit complicated, but it should go fast and it is probably faster than any other method.

[BigBoy1]

Paul A. -- I was about 15 minutes late in my suggestion. It was going to be very similar to yours. I guess great minds think alike!!!!