After looking at the sorting algorithms in the Source Code Repository I was inspired to make a contribution myself. I choose to make an implementation of the JeffSort algorithm. (Not this one but this one! )

It was done from memory before I found that page, so it might not be quite right.

On that page Jeff claims it's an O(1) algorithm, but as far as I can see it's really O(n)... but I'm not sure i remember how that O(x) stuff works so maybe I'm wrong... or maybe I've made a different sorting algorithm

Anyway, here is what I came up with:
It seems to do what it's suposed to from my testing, but it's not unlikely I've missed something. I'm sure you guys could think of lots of optimizations, so if you have any sugestions, I'm all ears.

Oh, and I'm probably way off on that cycle count, so if anybody could check out that I would be gratefull. I think each additional element should add the same amount of extra time (except when going from 255 to 256 elements, a a few cycles is saved there because of the 6502s lack of BRA opcode . Also, if there is 256 identical elements, then it will run a lot faster than when there is 256 varying elements because nothing gets written. That however only happens with 256 elements, not any fewer. I think, I'm probably wrong )



Edit: Decided to include the code from Jeffs page to show what the algorithm is suposed to do:

Looking at that I realised that maybe I should have included rangehi and rangelo as parameters in my implementation to speed it up. And maybe I should do a version for signed numbers too...

I haven't tried your sort algorithm, I'm only commenting on the O stuff. O(1) I believe would mean that the algorithm takes a fixed amount of time no matter how many elements there are (which, as you might imagine, nobody really talks about because it's silly). O(n) is linear, and O(n^2) is square, in other words, the amount of time an algorithm takes is porportional to the square of the number of elements. Insertion/Bubble/Selection sorts are O(n^2). Quick sort and Binary Tree sort are between O(n*log(n)) and O(n^2). AVL Tree is O(n*log(n)), which, in my understanding, is as good as sorts get. Therefore I am skeptical that your sort is O(n), which would beat O(n*log(n)), but I could be wrong.

Scott

Thank you for your reply. I've tested the execution time now, and after the large constant time part, it does increase linearly with the number of elements. (and the order of the elements doesn't matter; no worst case, always identical execution time for any given size)

But the way it achieves this could be called cheating. The algorithm doesn't actually do any sorting, it just counts how many elements there are of each value, and then it makes a new table with that many elements of each value.

So, as far as I can see, it's usefullness is very limited. You can't use it to sort a bunch of objects depending on a value in that object. (Example: trying to sort x,y,z vectors acording to z wouldn't work). In fact I can't really think of any situation where it could be used.

But if you encountered a situation where it could be used it could be a huge timesaver. The Combination Sort example in the Source Code Repository mentioned 2 second sort time for bubble sort, and 0.2 second for Combination Sort on an 255 element array. My code only uses ~0.02 seconds on a 255 element array on a 1Mhz C64. The Optimal Sort code used 0.0642 seconds, but that was on a 8Mhz device.

So, despite it's limited usefullness, it's still an interesting example because of it's speed.

An interesting algorithm, but the complexity is misleading because depends more on the range of the values than the number of values to be sorted.

For example sorting 20 values in the range (0-255) takes 256 iterations to clear the counts, 20 iterations to count the value frequences and 276 iterations to regenerate the sorted data.

If the range was increased to word size (0-65535) then aside from the fact that we might not have enough memory to store the counts, the number of iterations increases to 65536, 20 and 65556.

In can see that under some very specific conditions (e.g. small range and small number of values) that this may be the optimal solution but it lacks the generality of the other sort algorithms.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

> After looking at the sorting algorithms in the Source Code Repository I
> was inspired to make a contribution myself. I choose to make an
> implementation of the JeffSort algorithm.

I'll throw in a few free optimisations for you:

ldx #0
fill ;tya
;cmp temp,x
cpy temp,x
beq next
;txa
;sta (buffer),y
stx (buffer),y
iny
bne fill

Saves a couple of cycles,
Sprow.

Thank you for the sugestion, but according to http://www.6502.org/tutorials/6502opcodes.htm the 6502 has neither a cpy $xxxx,Y nor a stx ($xx),y instruction as far as I can see...

Bitwise, thank you for you reply. I have some comments to what you said, but I'm a bit busy now, so I'll post it in an hour or two from now...

OK, now I don't really remember what I was going to say...

That's not always true. If the number of values to be sorted are larger the their range, then it depends more on the number of values to be sorted than the range.

Yes, increasing the range to a full 16 bits would make the counting buffer too large. But what about sorting a larger number of 8 bit values? Sorting 64000 8 bit values would require 256 iterations to clear the counting buffer 64000 iterations to count and 64256 iterations to regenerate. I'll think I'll go an make new version for sorting more than 256 values now...

Yes, the range has to be small for this to be an optimal solution, but I strongly disagree with the 'small number of values' part. On the contrary, the algorithm is most optimal for large number of values. However I'm still unable to think of any situation where it could be usefull... But instead of trying to find a problem to the soultion, I thought I would share the solution, you never know, it might prove useful for somebody...

Here is a new version that can sort much larger arrays of 8bit values:
It seems to work, I'll do some more testing, comments are greatly appreciated.


Edit: Warning! This code is buggy, don't use it!

> > Saves a couple of cycles
> Thank you for the sugestion, but according to 6502opcodes.htm the 6502 has neither a [b]cpy $xxxx,Y[/b] nor a [b]stx ($xx),y[/b] instruction as far as I can see...

My brain sort of said that was the case, and the assembler didn't complain when I typed them in in interactive mode, but I guess I should have got up off my chair and got the opcode chart out - you're right of course!
Sprow.

I experimented with the first (small array) routine a bit and came up with a few optimizations. Here is the new routine:



The cycle count (which I've measured) assumes that branches and LDA (BUFFER),Y do not cross a page boundaries, and that TEMP starts on a page boundary. The NOP at line (B) was added just to make the formula neat and can be deleted to save 2 cycles (except when N=1). I like to use a TYA at line (A) instead of DEY. You would then call the routine with Y=N-1, so that Y=$00 when N=1 and Y=$FF when N=256. I prefer that to using Y=$01 when N=1, Y=$FF when N=255, and Y=$00 when N=256.

As for the optimizations, in the second section, we can get rid of the CPY #$00 by handling the last element specially, which saves 2*N cycles. In the third section, we reduce the TEMP buffer to 256 bytes by comparing Y to a zero page location rather than to TEMP,X which means we don't have to put Y in A for the comparison. In a sense, we're taking the 257th byte of the buffer and moving it to the zero page. At SORT6, Y = INDEX and the carry is set, since we always get there by a CPY INDEX that is equal, so instead of adding the count (TEMP) to the index, we store the negative of count in TEMP and subtract TEMP from INDEX, i.e. INDEX=INDEX+count is the same as INDEX=INDEX-(-count). Note that we enter SORT4 the first time with Y=0, so INDEX = TEMP the first time through. Finally, rather than jumping back to the first CPY, we simply add another CPY which allows us to tighten the SORT5 loop.

One easy way to save a bunch of cycles is to change the first section to:



which saves 640 cycles, and adds only a single instruction. You can unroll the loop a bit more and save an additional 320 cycles with:



Which adds an additional 7 bytes to the routine, so you'll have to decide where the point of diminishing returns is.

The second (large array) routine has three bugs.

1. LDY #0 should be moved before the label COUNT, since Y is not initialize before then.
2. BUFFERLENGTH is not decremented properly.
3. BUFFERSTART (in the FILL loop) must be incremented every time you store, so it must come before the BCC F2

After fixing and tweaking it, this is what I ended up with (I haven't counted or measured cycles on this one, but the timing isn't going to be perfectly linear with all the high byte updating anyway):



Note that this uses one fewer zero page location. You can free up the zero page location used by BUFH by using PHA and PLA which only adds 1 cycle.

This routine is fairly tricky. It does decrement properly even though it may not look like it. It makes use of the fact that:



loops NUM+1 times. If you print the value of NUM inside the loop, you'll see that it counts funny, but it does loop NUM+1 times. This works because



counts NUM times if NUM is non-zero, or 256 times if NUM is zero. By adding an INC NUM before the loop, it will count NUM+1 times if NUM was 0 to 254, or 256 times if NUM was 255, so it counts NUM+1 times in all cases.

In the SORT2 loop, we want to loop BUFFERLENGTH times, not BUFFERLENGTH+1 times, so we prepare BUFFERLENGTH, with the INCs, then decrement once.



Moving the INC BUFFERLENGTH+1 to the end doesn't change the final result.



This is the same as:



but BUFFERLENGTH+1 is incremented when BUFFERLENGTH is non-zero, and unchanged (incremented then decremented) when BUFFERLENGTH is zero, so we can change it to:



The SORT5 loop is also very sneaky. We want to branch to SORT9 if the count is zero, and loop count times, not count+1 times. Using the previous optimization, we start with:



The BNE LOOP6 can be changed to branch to the INC since with already know that TEMP,X is non-zero.



Now when we fall through to the second LDA TEMP,X, we already know that LDA TEMP,X is non-zero, so we can replace it and the BEQ SKIP2 with a BNE SKIP2



To get rid of the BNE SKIP2 we'll move the INC TEMP+256,X before the LDA TEMP,X and then undo the INC after the branch:



The LDA TEMP,X is now unneccesary, since DEC TEMP+256,X affects the Z flag. The INC TEMP+256,X will be performed one time for each value of X, so we can eliminate the INC TEMP+256,X by initializing the TEMP+256 buffer to 1 rather than 0, leaving us with:



Finally, note that we're not using a CPY INDEX like we did in the small array routine. It might be possible to further optimize the large array routine by using a CPY INDEX to replace DEC TEMP,X at SORT8, since the CPY will be faster than the DEC.

If anyone has questions about any of this (hopefully my explanations aren't too terse), please feel free to post or drop me an e-mail.

I remember my algorythms class...

Traditional sorting algorythms can sort any arbitrary set of operations using only swapping and a single comparison.

This is different, so it can be much more efficent. There's a whole load of algorythms that are designed to be more efficent over data where you have values.

Still, In the rather large stock tracking application that I work on in the Day Job, there's lots of sorting but none of the sorts could be replaced with that sort. It's also not particularly memory efficent.

wow, great work with those optimizations dclxvi! There really isn't much to add after a great post like that...

Yeah, you're right. My test cases worked despite those bugs; in other words they were poorly choosen. I fixed those bugs, so now I hope it's actually working... It ended up looking a bit like your code, except not quite as optimal (of course), and I solved bug #2 by inverting BUFFERLENGTH and counting up instead of down. It seems to work, but I'm sure I've managed to introduce a few new bugs in the process I think your version is better anyway...

I think you're on to something, but right now my brain hurts just trying to think about it...

Anyway, thanks for the enlightening reply.

Edit: I realised you can speed up the counting loop in the large array version by using a end of array pointer instead of a length of array variable. I gained 2*n cycles, I think...

> 3. BUFFERSTART (in the FILL loop) must be incremented every time you store, so it must come before the BCC F2

I got this one wrong. The problem is that the byte after the buffer will be overwritten. For example, if the count is 1, we store the byte, subtract 1 (which sets the carry), increment the buffer pointer, store the byte, subtract 1 (which clears the carry), then branch to F2. The correct solution is to move the two instructions at F1 after the BCC so that only one byte (for this case) gets stored.

Anyway, Here is a different method that is faster in most cases. In the second section of the small array routine, replace both DEC TEMP,X instructions with INC TEMP,X instructions, then replace the third section with this:



The worst case is a 256 element array that contains each value just once. In this case, the new routine will be 2 * 256 cycles slower than the old one. However, by specifying that the buffer must be located on a page boundary (since the maximum buffer size is 256 bytes, this isn't an unreasonable restriction), we can get rid of the three instructions before SORT6 and this method is faster in all cases as far as I can tell. (Actually, as long as the low byte of the buffer address + the buffer length <= 256 we can still eliminate those three instructions.). Note that INDEX is no longer used, which frees up that zero page location.

We can apply a similar technique to the large array routine. Another optimization is to work a page at a time when possible. Actually, this is a good optimization priniciple for practically any 6502 routine. We win big time in the middle section, since there will usually be at least 256 elements. In the last section, we can only work a page at a time when the count is at least 256, which is possible, but not as likely.

Since the three major sections have all changed, here is the new large array routine in its entirety. There isn't anything especially tricky this time around.



Even though from SORT11 on it's basically the same as the new third section of the small array routine, note that the SORT10 loop makes use of the fact that Y=0 upon entry, so the INDEX method can't be used at SORT11 as is. Note that the first section is faster than it was previously, which compensates for the worst case of the small array routine (a 256 element array containing each value just once). Also, note that the three instructions before SORT13 are now necessary, since the buffer can be greater than 256 bytes.

Finally, here's one last optimization suggestion (which I haven't applied above) that can be applied to a lot of routines. For speed, the usual:



isn't really optimal since most of the time the branch will be taken. If the code is rewritten as follows:



that branch is not taken most of the time. It looks ugly and can make a program more difficult to follow, but it will save 251 cycles (assuming the branch doesn't cross a page boundary) for every 256 times it gets executed.

I checked the execution time for the new "Shell Sort" algorithm of the software repository provided by Fredrik Ramsberg. My first test was to sort a random permutation of the values 0 - 255.

1398 *256 oscillator periods were needed corresponding to 0.0447 seconds with 8 MHz. Corresponding figures with the simple algorithm I provided the software repository with earlier are 2006 *256 oscillator periods corresponding to 0.0642 seconds.

Then I sorted 8192 values (16384 bytes) with "Shell Sort". For this 87503 *256 oscillator periods corresponding to 2.800 seconds was needed. The ratio 1398/(256 * ln 256) = 0.180 and the ratio 87503/(8192 * ln 8192) = 0.110 .

But trying to sort even more values there is a problem! There seems to be some bug in the program that only shows when many values are sorted!

Sorting for example 10000 values the subroutine returned prematurely with only a part of the sequence sorted. The input data was a permutation of the values 0 - 9999 properly in RAM $1183 - $5FA2.

Everybody (specially Fredrik Ramsberg) is invited to verify my results! And provided I am right, the code should be corrected.

If somebody ( Fredrik Ramsberg!) wants to have my test data send me a private message with email address!

Mats,

I hadn't discovered the forum until now (I haven't been a frequent visitor until now, but now that I know there's a forum, that might change).

Glad to see your test results. I'd quite like to have your test data, so I can reproduce the bug. My address is fredrikXyzzYramsberg.net (replace XyzzY with "@" to get the real address).

I did spot that my Shell Sort was gone from the repository, and mailed Mike about it, but he didn't reply or his reply didn't reach me.

I think the bug has to do with using the highest value of h. If that is true, then sorting less than 19682/2 values should always work correctly, while a greater number of values may fail. I don't know what the bug is yet though. The code is still available here:

http://www.6502.org/source/sorting/shell.htm

I intend to return after further investigations.

Best regards,

/Fredrik