One of my early CS classes had us graph results of sorts and plot the order of magnitude...quicksort and mergesort were fairly even, depending on the "randomness" of the data, and were very close to n*logn on the graph. There were a couple of other variants of recursive sorts as well, but I've never really used anything but the basic quicksort in a real live application... On Wed, 1 Mar 2000, Dwight Elvey wrote:

Aaron Christopher Finney <af-list(a)wfi-inc.com> wrote: Hi I always wonder why they don't teach kn+c type sorts. QuickSort and MergeSort are good for things in the 50 to 500 count someplace but even for large data fields, the kn+c will win over a k(n*logn), even if the k and the c are somewhat large. The two sorts that I've always liked for large data sets are either a radixed basket sort or a radixed distribution sort. The radixed basket sort is one of the oldest ( ever watch a card sorter? ). With the larger memories of machines today, even large data fields can be recursively sorted faster than QuickSort could do. This is because, n*n > n*logn > n for large n's. Both, basket and distribution, are of the form kn+c. The c can be large so small numbers of items are not practical. In the code I wrote, about 1 millisecond was the c ( the fixed over head), so you can see that for something in the 100 integer range, QuickSort would, most likely, have been faster. Dwight

John Wilson &lt;wilson(a)dbit.dbit.com&gt; wrote: Hi John Radixed sorts are just normal sorts that you break the problem into a number of smaller task. Normally if you break the original problem into something like the square root or some other root of the problem, it is more efficient. In the example of 16 bit integers, breaking the problem into two sorts of the 8 bit fields is quite fast. In this case it would be called a 256 Radixed sort. Not all sorts gain speed up by using radixing. You need a sort that doesn't destroy the partial order created by the first pass sort. The trick with both the basket and the distribution sort is that you don't make any comparisons, you just put the items into the correct location. You don't need to compare to any other items ( all 5's go in the 5's slot, regardless of how many 4's or other 5's or 6's ). The basket sort on a computer usually requires creating a number of linked list to build the results in. The distribution sort requires one to build a tally of the number of each item type in each basket location. This has the advantage that you know ahead of time where to put the item being sorted. It does have the overhead that you need to make a pass through the data to find the tallies. Both of these methods require building data structures that are used for book keeping by the sort algorithm. This is where the over head comes in. Creating these separate data structures takes time and uses a reasonable amount of space. This was a problem when computers were considered large with 16K words of memory. Now days, I have a machine infront of me with 1GByte and I only use a small fraction of it. Still, this part in time is usually constant and the time cost for each item is small. Since both of these types of sorts have nothing that does anything different ( no conditional flow ), they take a fixed amount of time to handle each data item. This is even better on the newer piped machines because they hate conditional branches. This means that for large enough data sets, k1*n+c will be smaller than k2*n*log(n), when n is big enough that k1+c/n < k2*log(n). As you can see, for large n, c/n gets quite small. So we can say k1 < k2*log(n) is a rough guide for how large a data set will be best sorted. If enough request, I can post code showing both types of sorts. Dwight

John Wilson &lt;wilson(a)dbit.dbit.com&gt; wrote: I'd have to disagree with him about the obviousness. It seems perfectly obvious to me that if you keep swapping out-of-order elements long enough, eventually a list will be sorted. It also seems obvious that if you do this systematically by scanning the list from one end to the other repeatedly, that it can take no more than n-1 passes, the time it would take an element to move from one end of the list to the other. The only other in-place sort that seems more obvious to me is: for (i = 0; i < (n-1); i++) for (j = (i+1); j < n; j++) if (a [j] < a [i]) swap (& a [j], & a [i]); which has the disadvantage over bubble sort of doing more swaps. A Shell-Metzner (sp?) sort is substantially more efficient but also much less obvious.

"Fred Cisin (XenoSoft)" &lt;cisin(a)xenosoft.com&gt; wrote: Hi Usually I first sort the new data and do a merge, which is essentially a single pass bubble sort. Dwight

Which is the sort that probably 90% of CS101 students come up with before they know what a sort is... Ah, and no one has mentioned a heap sort yet (aka sift sort, or Williams sort), which has the advantage of predictability (always NlogN) and no such thing as a worst-case scenario, where as quicksort and shell sort both have the capability of being N*N. Aaron

You wrote.... When I first fell in love with probability and statistics (high school), the first thing I would do on any new computer I came into contact with was run a chi squared distribution program on it so I could find the bias of the random number generator in the system. Then anytime I used the rand() or RND() or whatever that system called it I would apply the correction to ensure a better "random" distribution. I would love to find a copy of the program I wrote to do it. I decided to make it interesting to watch too - it painted an ascii pyramid on the screen and dropped "balls" from the top center and randomly hit each "pin" on the way down much like a pachino machine. You'd get your distribution at the bottom via a count on each final chute! Jay West