RADIX SORTING TUTOR Version 1 jmX Opiate Introduction ============= Well, many of you may already know what radix sorting is and how it is done, but for those of you who don't, this tutor is for you. I just recently found out how it was done, so I am no expert on it but it is a fairly simple concept and i'll do my best to present it as one. Lets get started. What is it? ============ Radix sorting is a method of sorting numbers without using compares (ie =, <, >, cmp, etc..). It is that fact that makes it one of the fastest sorting routines out there for sorting a list of numbers. As far as I know, some of the fastest 3d engines out there use radix sorting when dynamic 3d data is being used. If your data is static (ie...walls in a dungeon ala doom) then BSP trees are the way to go as far as that data is concerned. But, if your objects are moving around and morphing, then radix is a good way to sort. How its done ============= The radix sorting I will talk about in this doc is done on the BIT level. We will sort a list of numbers by looking at the seperate bits that make up a number. To understand how it works, you must understand binary numbers - which I'm sure we all do. I'll explain it the way I was taught.....with a concept of "buckets". Lets say we have a list of 4 8-bit numbers. First, what we do is look at the least important bit of each number. This is either 1 or 0. We put all the 1's in one "bucket" and all the 0's in another. Now, we merge the 2 with the 0's bucket appearing first. Now, use the 2nd least significant bit and resort back into the 1's and 0's buckets, then merge with the 0's bucket first. After we do this 8 times (for 8 bit nums) we will have a sorted list. It is just that simple. I hear some of you saying "buckets? wtf!" ok..well, that is understandable, so let me show you an example. Example ======== Lets say we have a list of 8 numbers: Decimal Binary ------- ---------- 23 (00010111) 184 (10111000) 7 (00000111) 253 (11111101) 105 (01101001) 217 (11011001) 89 (01011001) 166 (10100110) First what we'll do is use the LSB (Least Significant Bit) or rightmost bit to determine if the number goes into the 1's or 0's bucket or list. We just go down the top of the list and go to the end...makes sense eh? Here are the 2 buckets after we separate them for the first time. I will use the binary versions of the numbers until we have finished sorting. Ill put an asterisk above the bit we are curently looking at. 0's Bucket 1's Bucket ----------- ---------- * * 10111000 00010111 10100110 00000111 11111101 01101001 11011001 01011001 Now, we merge the 2 lists into one, with the 0's bucket going first. Merged List after BIT 0 pass ============================= 10111000 10100110 00010111 00000111 11111101 01101001 11011001 01011001 Now, we repeat the whole process over for the 2nd least significant bit, or the second bit from the right. Again, its important that we do this in order of our merged list, going from the top down. 0's Bucket 1's Bucket ----------- ---------- * * 10111000 10100110 11111101 00010111 01101001 00000111 11011001 01011001 Merged List after BIT 1 pass ============================= 10111000 11111101 01101001 11011001 01011001 10100110 00010111 00000111 Ok, now the 3rd bit. Gee, this is tiring. 0's Bucket 1's Bucket ----------- ---------- * * 10111000 11111101 01101001 10100110 11011001 00010111 01011001 00001111 Merged List after 3rd pass ============================= 10111000 01101001 11011001 01011001 11111101 10100110 00010111 00001111 4th PASS. 4th bit from the right. 0's Bucket 1's Bucket ----------- ---------- * * 10100110 10111000 00010111 01101001 11011001 01011001 11111101 00001111 Merged List after 4th pass ============================= 10100110 00010111 10111000 01101001 11011001 01011001 11111101 00001111 5th PASS. 5th bit from the right. 0's Bucket 1's Bucket ----------- ---------- * * 10100110 00010111 01101001 10111000 00001111 11011001 01011001 11111101 Merged List after 5th pass ============================= 10100110 01101001 00001111 00010111 10111000 11011001 01011001 11111101 Now it is time to go get a soda and some cookies. ONLY 3 MORE TO GO! 6th PASS. 6th bit from the right. 0's Bucket 1's Bucket ----------- ---------- * * 00001111 10100110 00010111 01101001 11011001 10111000 01011001 11111101 Merged List after 6th pass ============================= 00001111 00010111 11011001 01011001 10100110 01101001 10111000 11111101 7th PASS. 7th bit from the right. 0's Bucket 1's Bucket ----------- ---------- * * 00001111 11011001 00010111 01011001 10100110 01101001 10111000 11111101 Merged List after 7th pass ============================= 00001111 00010111 10100110 10111000 11011001 01011001 01101001 11111101 ********************** FINAL PASS!!!!! 8th bit from the right, or the first bit on the left ********************** 0's Bucket 1's Bucket ----------- ---------- * * 00001111 10100110 00010111 10111000 01011001 11011001 01101001 11111101 Merged List after FINAL pass ============================= 00001111 = 7 00010111 = 23 01011001 = 89 01101001 = 105 10100110 = 166 10111000 = 184 11011001 = 217 11111101 = 253 Whew! IT WORKED! ================= Ok, now that you see how the example worked you may be saying "geez, that was a lot of work, how is this faster than other sorting methods?" First off, this method uses NO COMPARING. That is one of the most important issue. Also, some soring techniques slow down logarithmicly with the number of objects you are sorting. Radix sorting loops increase linearly with the number of objects you sort, so, for large or lengthy lists you will see a large speed increase. How to implement in code ========================= Here is a sample implementation. It is simple, and it pre allocated 2 buckets that were large enough to hold all the numbers in the main list if needed. Other versions may use linked lists to save on memory usuage. Listsize is the length of the list of numbers to be sorted. The List array is the area that holds the merged list, and bucket0 and bucket1 are the 2 temporary "buckets" we discussed earlier. for (pass=0;pass<=7;pass++) { bitmask=1<