The thing is that it really does sort the data. I'm still trying to discover the terrible flaw in it, but after using it on a variety of initial data distributions I have not yet done so.
Random data produces the longest sort time, with any type of arranged data, backwards or forwards producing much shorter times. Its "worst case" appears to be random data.
Obviously the code I posted isn't an optimal version meant for use, it's just to show the principle.
And why 1.6 ? At first I thought it might be (sqr(5)+1)/2 for some mathematical reason I do not as yet grasp. But 1.605 or 1.595 etc give longer times. Whatever the magic number is it's pretty close to 1.6 for most data sets.
Random data produces the longest sort time, with any type of arranged data, backwards or forwards producing much shorter times. Its "worst case" appears to be random data.
Obviously the code I posted isn't an optimal version meant for use, it's just to show the principle.
And why 1.6 ? At first I thought it might be (sqr(5)+1)/2 for some mathematical reason I do not as yet grasp. But 1.605 or 1.595 etc give longer times. Whatever the magic number is it's pretty close to 1.6 for most data sets.