INSERTION SORT Is O(n log n) is the name of a paper by Michael A. Bender and others where they discuss an improvement to Insertion Sort by leaving gaps between insertions so that the list does not have to be moved each time a new item is inserted into the lower part of the list.
Wikipeadia calls this a Library Sort or a Gapped Insertion sort which is not at all the same idea as the gaps used with a shell sort.
Unfortunately, no code was included in the paper and i have seen no implementations of this Library sort.
I am sure that I can write my own but as I am lazy and busy, I won't be able to start work on this for a couple of weeks.
Anyone that either writes the code or posts an implementation of the algorithm in any popular language (ie.. C, C#, java, C++, Visual Basic, etc...) will get my grateful acknowledgement of their superior skills plus a cool 500 points. :)