Root Sort

The Root Sorting algorithm by Jeremiah Tatro


The Root Sorting Algorithm is an algorithm I designed to improve on the Bubble Sorting Algorithm by the observance that

the reason the bubble sorting routine is so inefficient is that it doesn't do enough work per pass of the array to be sorted.

I was thinking of different ways to improve its efficiency by knowing that if you start by swapping the greatest valued element

in the array, it will be the only element that is moved into its proper place per pass. The big O of the Bubble Sort is O(N^2).

The best sorting algorithm can sort in O(N*Log(N)) however they have various problems, like the complexity of the tree sorting,

The chance that an algorithm could be sorted in N^2 (like what happens when the Qsort is partially sorted) and be easily

implemented by hardware are reasons that someone might want to use the Root Sort over other algorithms. However the most

powerful reason for its use, is in academia it is easy to understand and teach student about sorting routines.

The Root Sorting Algorithm stems from the idea of having a glass box of rocks and sand shook back and forth allowing the

heaviest stones to fall to the bottom of the box. I has been showned to have a big O to be O(N*Root(N)) which is tremendously

faster than a bubble sort but not as fast as a Qsort or Tree Sort.

For a demonstration of the algorithm see my code down load.