Big oh statistics for maximum moves of new patented sorting algorithm better than heap sort

From posting@sci.math.research: > > From the abstract of US Patent 5,926,815, issued > July 20, 1999, "BINARY SORT ACCESS METHOD AND > APPARATUS": > > "The binary sort access method and apparatus makes > use of a binary search to show where an item of data > not found should be placed in sorted order within a > list in a table in memory or in a file ... When no > blank table entry is available items of data are > moved to make room for the next succeeding item of > data. A partially filled or filled list of items > may be rewritten again to provide one or more blank > table entries between each item of data." > > From the detailed description of the invention: > > 1. The apparatus keeps data items in physically > sorted order. > > 2. To avoid (or delay) moving on average n/2 items > whenever an item is inserted in sorted order into > the list, sorted items initially have eleven blank > spaces inserted between each item, making the space > required as n + 11 * n or 12 * n. > > 3. When the particular group of eleven empty or > partially filled blanks is determined, the new item > is put there with a straight insertion sort. > > 4. Whenever an area of eleven originally blank > items is filled up with physically sorted items, the > entire list is rewritten with eleven blanks again > interspersed between each physically sorted data > item. > > What are the Big-oh statistics of this sort for: > > 1. Worst (maximum) number of comparisons; and > 2. Average run time and worst (maximum) run time. > > No one has come up with any meaningful statistics, > possibly because no one really has taken the time to > understand fully how the sort works. The maximum number of moves is N * ( ( b - 1)/2). The maximum number of moves with rewrite of the sorted list is: N * ( ( b - 1)/2) + ( INT( N / b) * b) where b is the number of blanks used. In contrast to a heap sort (the best performer for number of moves at n lg n), for b = 11, the above algorithm has over 40% fewer moves.