# Efficient sorting **URL:** \ **Category:** Factual Questions\ **Created:** [September 1, 2002, 2:50pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564 "2002-09-01T14:50:24Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![AWB](https://avatars.discourse-cdn.com/v4/letter/a/bb73d2/32.png) [@AWB](https://boards.straightdope.com/u/AWB)\ **Post date:** [September 1, 2002, 2:50pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564/1 "2002-09-01T14:50:24Z")
In computer science, we studied various algorythms for sorting list and arrays efficiently. But what is the most efficient way to _physically_ sort objects? My problem: every work day, I have a rack of dry cleaning to sort. Each bag is numbered as to its location on my route. Many stops have multiple bags, so locating the second and subsequent bag is easier: it just has to go next to one of the previous ones for that stop. This brings up a secondary question: is there any software out there, similar to Mapquest, that will determine what the most efficient route is for a list of addresses within a city? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 1, 2002, 3:59pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564/2 "2002-09-01T15:59:33Z")
Personally, I use mergesort to do real objects, with a slight modification: small enough groups are sorted directly, using (roughly) insertion sort. In answer to your secondary question, there probably isn’t, as the traveling salesperson problem reduces to that. There might be approximation software, though; you’ll have to keep looking. ---
**Author:** ![jdc](https://avatars.discourse-cdn.com/v4/letter/j/919ad9/32.png) [@jdc](https://boards.straightdope.com/u/jdc)\ **Post date:** [September 1, 2002, 5:44pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564/3 "2002-09-01T17:44:38Z")
You could check out XMAP Business from Delorme. It does route planning. Not too expensive, $99 as I recall. My Church used it to plot addresses for a Christmas tree pickup fund-raiser. We did not use the route plotting feature, however, as it was easier to plot these by hand. A more expensive option is Maptitude ($495) w/ a $10,000 route optimization add-on (Trans Cad). [www.caliper.com](http://www.caliper.com) ---
**Author:** ![Sam\_Stone](https://avatars.discourse-cdn.com/v4/letter/s/ecccb3/32.png) [@Sam\_Stone](https://boards.straightdope.com/u/Sam_Stone)\ **Post date:** [September 1, 2002, 6:28pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564/4 "2002-09-01T18:28:07Z")
**AWB** : What differences between physical objects and objects in a computer do you think effects the efficiency of sorting? The math is the same. The number of iterations to sort 10 real boxes is the same as the number of iterations to sort 10 ‘box objects’ in a computer. In the real world, efficiency might be determined by the types of machines available to do it, the size or shape of the objects, etc. Those are practical concerns, and they’ll be different for everything. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [September 1, 2002, 11:49pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564/5 "2002-09-01T23:49:04Z")
**AWB** : first note that finding duplicate/adjacent tags is just a difficult as sorting. They are provably “the same problem” to us Computer Scientists. The best sorting algorithm _always_ depends on the properties of the data. There is no one best method. You have not given enough information about the keys (tag numbers). If they are (a) short, like at most 4 “important digits” (maybe 10 total digits but only the last ones vary in a given batch) and (b) in a small range like 0-9, then radix sort: Put them in 10 piles based on the last digit. Stack the 10 piles back into 1. The ‘8’ pile on the ‘9’ pile, the ‘7’ pile on those, etc. Repeat the above for the next to last, then then 3rd from the last, etc. digits. Note: do NOT start with the first digit. Obviously, the more “important digits” and the larger the range (like letters) the worse this is. If the items are already “almost sorted” then Insertionsort works best. Stay away from Shellsort. And remember, Quicksort is to sorting as Greenland is to real estate. Me? I like a well tweaked Heapsort. But I’m a well tweaked kind of person. ---
**Author:** ![DarrenS](https://avatars.discourse-cdn.com/v4/letter/d/977dab/32.png) [@DarrenS](https://boards.straightdope.com/u/DarrenS)\ **Post date:** [September 2, 2002, 3:05am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/6 "2002-09-02T03:05:41Z")
> [@](#): > > This brings up a secondary question: is there any software out there, similar to Mapquest, that will determine what the most efficient route is for a list of addresses within a city? This is known in computer science as the [Travelling Salesman Problem](http://www.math.princeton.edu/tsp/) and, at least when I studied CS, couldn’t be solved for the general case. You can attack it heuristically however, and the site I linked to above shows a solution for 15,112 cities in Germany. Sorry, I don’t know of any software that solves it “numerically” - perhaps Mapquest offers a “web service”? (depending what your budget is) ---
**Author:** ![AWB](https://avatars.discourse-cdn.com/v4/letter/a/bb73d2/32.png) [@AWB](https://boards.straightdope.com/u/AWB)\ **Post date:** [September 2, 2002, 4:22am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/7 "2002-09-02T04:22:05Z")
> [@](#): > > \*Originally posted by Sam Stone \* > \*\ ***AWB** : What differences between physical objects and objects in a computer do you think effects the efficiency of sorting? \*\* Lots of differences. For instance, say you had two groups of bags, each one sorted (like the last step before the final merge of a merge sort). In a computer, it’s nothing to copy the data from one array then the other, merging them into a final sorted list. But physically, it’d be completely inefficient to keep going back and forth seeing which group’s lead item is the next to go in the master group, pick it up, and hang it 20-30 feet away, then go back and see which of the groups has the next. The data (the bag numbers, for whever asked) are simply numbers from 1 to 200 or so, directly related to my manifest’s stop numbers. ---
**Author:** ![Urban\_Ranger](https://avatars.discourse-cdn.com/v4/letter/u/e9c0ed/32.png) [@Urban\_Ranger](https://boards.straightdope.com/u/Urban_Ranger)\ **Post date:** [September 2, 2002, 5:07am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/8 "2002-09-02T05:07:56Z")
Heapsort will be good for this 😃 Seriously, if you have a small number of bags and they are nicely ordered (say, in a stack) then a selection sort works pretty well. ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [September 2, 2002, 6:42am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/9 "2002-09-02T06:42:48Z")
What’s so bad about bubble sort? :: G, D, & R L H ::: ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 2, 2002, 6:47am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/10 "2002-09-02T06:47:54Z")
Stoogesort is more elegant. ---
**Author:** ![AWB](https://avatars.discourse-cdn.com/v4/letter/a/bb73d2/32.png) [@AWB](https://boards.straightdope.com/u/AWB)\ **Post date:** [September 3, 2002, 2:17am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/11 "2002-09-03T02:17:29Z")
> [@](#): > > \*Originally posted by Derleth \* > \*\*What’s so bad about bubble sort? \*\* I only have half an hour to spare in sorting them. 🕶 If I had a perfect memory (which I don’t), I might try doing a sort of bubble sort: instead of swapping every time I found an item that belonged to the beginning, I’d just walk along all my bags and remember where the lowest unsorted bag was. When I reached the beginning, I’d then run back, pick up that bag, and place it at the beginning. Then I’d do the reverse: walk back and remember where the highest unsorted bag was, then place it once I reached the end. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [September 3, 2002, 2:17am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/12 "2002-09-03T02:17:57Z")
> [@](#): > > Stoogesort is more elegant. Is that related to Bogosort? Which has a linear best-case efficiency, you know 😉 ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 3, 2002, 2:48am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/13 "2002-09-03T02:48:20Z")
> [@](#): > > \*Originally posted by Chronos \* > \*\*Is that related to Bogosort? Which has a linear best-case efficiency, you know 😉 \*\* Well, the one advantage of stoogesort is that it’s guaranteed to terminate. Course, you’re splitting hairs any time you call that an advantage. Anyway, stoogesort only seems to show up in problem sets, so I’ll describe it. It’s a simple recursive algorithm. If you’ve got two elements, sort them directly. Otherwise, you sort the first two-thirds of the list, sort the last two-thirds of the list, and then sort the first two-thirds of the list again. I leave it as an exercise to the reader to prove that stoogesort is correct, and superquadratic. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [September 3, 2002, 7:30am UTC](https://boards.straightdope.com/t/efficient-sorting/126564/14 "2002-09-03T07:30:30Z")
> [@](#): > > \*Originally posted by Chronos \* > \*\*Is that related to Bogosort? Which has a linear best-case efficiency, you know 😉 \*\* I thought bogosort had an order 1 bestcase efficiency. theoretically, you could do it in one go. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 3, 2002, 2:34pm UTC](https://boards.straightdope.com/t/efficient-sorting/126564/15 "2002-09-03T14:34:12Z")
Takes linear time to verify that the list is sorted, y’know?