Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


JT
Posts:
1,448
Registered:
4/7/12


Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 5, 2013 10:22 AM


I do intend to implement this one, i think it will beat any other algorithm for any amount of elements *and element size* when sorting above 20003000 elements. I can not guarantee it will not be faster at smaller amount of data too...
By creating a pointer binary tree with each leaf holding a integer, you move the binary numbers to the tree from least digit to highest using left legs for 0's and right for 1's. (Basicly creating leaves for new numbers, and at last digit you add 1 to the leaf slot. So after you moved all values into the tree and created all the nodes, you simply read out all the none zero values holded into the slot of the leaves within the binary tree.
Now to the problem and solution, using a tree reading in the values, they will not be read in from lowest to highest because the legs will differ in length and they will be unordered in the tree. The solution to the problem we create a single leg (heap) ***for each digit***, so numbers with digit 9,10,11.... digits and so on run in their own legs. Our binary tree will be sorted as we read in the values and we just need to read it out from left to right. This is probably within the first courses of information theory, so the question is why have this not been applied to sorting problems before?
Can anyone estimate the time complexity of this algorithm, and it seem to be a general purpose algorithm, the biggest challenge will be to find a programming language that have dynamic memory for data structures of binary tree type.
Is this also a radix type of sorting?



