Content deleted Content added
Line 728:
Traditionally it is thought a "triangulation sort" cannot be fast because it needs two or thee dimensions to compare characters (also no cpu strcmp to use). However it gains by never comparing two things twice. That still lags behind merge sort best case, but does win in some cases.
"hsort" or headsort can win in a few major ways.
"hsort" or headsort wins in TWO major ways. first: when the first bin is done (which is triangulated and cannot finish sooner), headsort program can begin piping sorted output. (unlike a simple "sift up" sort, it can finish the tail quickly as well).▼
▲
ONE: "hsort" found two NEW improvements which may well make it a good algo to use in general. First instead of data[line][field][characters] it tried data[field][line][characters] and nearly being deleted attempt: found a special case which allowed a dimension reduction of 1, at moderate cost (a good improvement). Doing so ate up all time to try the other...▼
▲
TWO: Next and recently, HSORT tried a simpler dimensional reduction. Using a 1d array sorted that output ptr to 3d array. Impossible per say: but distribution counting allows it on the tail, so it is fully 1/2 true.▼
▲
THREE: the old adage *foo[][][] is expesive is not as true as it had been in the 8086 days. New CPU can do some extra dimensions in 1 CPU tick, which remove more of the remaining handicap of the 'hsort' algorithm in practice.▼
▲
With those two (or fee) dimensional reductions my tests show that hsort beats "merge sort" used in gnu sort heavily in best cases, and also still wins in headsort's worst cases: just all around faster FOR multi dimensional sorting.
| |||