Date: 06/15/06 (Algorithms)    Keywords: java

Speaking of zany sorting algorithms...
I've managed to put together one of my own (probably best to be thought of as a mental exercise), and I really am not too sure on how to analyze its time complexity. It takes a rather unique approach to get the job done. The basic concept of the sort is that it calculates the mean, estimates the variance, and then throws each value to where they would belong in the array if they were in a normal distribution (more specifically it plugs the value into a function equivical to the cumulative distribution function to return a value between 0 and 1, and multiplies that value by the total elements in the array (converts this to an integer) and places the value in the corresponding position in the array). It starts sorting at the first value, then sorts the value that it replaced. It marks when an element has been replaced. When an element is replaced, it flags the location. If a value tries to go into a location that is flagged, it compares the values, and moves the new value to the left or right acording to if it is less or greater than the previous value. If the value to the left or right is also flagged, it makes this comparison, and if the value is going to move back the way it came from, it instead takes that spot and shifts all the flagged values over the direction it was initially moving. There are also left and right borders, which once crossed force this shifting to go the other direction as there is no more room. The left and right border value becomes the last location that was shifted. If a value is placed on the border, the border shifts by one. When the left and right borders meet, the array is sorted.

Here is a link to some not so clean java code that implements this...
http://dayreader.com/foo/statSort.java

Certainly, hardware is not optimized for this kind of sort, but I still am curious as to what kind of time complexity it creates for larger sets, or if there is a way to eliminate the memory use.

Source: http://community.livejournal.com/algorithms/77941.html