The Bubble Sort 2465

Charles Richmond

Hi Why not use a distribution sort. While quicksort works well for a small number of items, as the items increase in number, the distribution sort will overtake quick sort. The length of the sting also effects the speed of the distribution sort but for things like names in a mailing list, anything over about 30 or so and the distribution sort will blow away the quicksort. This is because quicksort is nlogn while the distribution is a n. Not counting the overhead, the distribution sort will run only twice the time for doubling the data size. As an example of speed comparisons, on a 1000 integer sort ( 16 bit signed ), the distribution sort ran about 15-20 times faster than a quicksort. The distribution sort doesn't see any change in speed if the data is ordered or not. It always runs in a factor of n, not n^2 or nlogn, just n. This is because there are no data depend decisions to make. One just analyses the data to be sorted an orders the data based on the order. The distribution sort has one flaw. It does take more memory than a quick sort. It also takes some clever optimizing for long length strings and varied length strings. Still, it will do quite well without this. The other thing that is interesting is that one can do just about any sort order with almost no speed penalty. For most sorts, one needs to pre-mung the data by translating to something that has the right sort order. The penalty in the distribution sort is just a small constant time, not related to the number of items, just the data width. Things like moving all the numbers after letters is a common sort problem or moving uppercase letters before lower case. Dwight