Mike has posted my sort program to the source page. I had it posted because many actually believe that QuickSort is the fastest sort. In the general case it is true except for special cases, like the data already being sorted. The sort I posted runs at an almost constant rate, regardless of what the data looks like. Data that has large blocks, that are the same, is the slowest, while random data is the fastest. It is still only a small percentage difference. The one I posted can have a few more optimizations but is still faster on 1K integers than the QuickSort posted in CodeBase64. It is several time faster for 12K of data ( almost 5 times ). It can be simplified to sort 256 chunks but isn't worth modifying to do smaller amounts. If you wanted to sort 1255 integers, you might just do 1280 ( 1024+256 ) instead. On the 6502 doing lesser amounts is clumsy. It is a large program and is not a sort in place type program. It requires two full sized buffers. It does have the advantage that one can do all kinds of out of order sorts for almost no overhead. This has advantages when you want to do things like sort lower case in front of upper case or sort numbers after letters. That ability by it self make it one of the best sort programs out there. It does slow down if you need to sort more columns. Then things like QuickSort can do better but if you need out of order sorts, it still shines with larger data. Please excuse my poor coding as I'm new to doing 6502 code. Dwight
|