Big-oh statistics for number of comparisons and run time of new patented sorting algorithm

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. Received on Thu Jul 29 1999 - 00:00:00 CEST